Some Results on Prime and k-Prime Labeling

Abstract

A graph G = (V; E) with n vertices is said to admit prime labeling if its vertices can be labeled with distinct positive integers not exceeding n such that the labels of each pair of adjacent vertices are relatively prime. A graph G which admits prime labeling is called a prime graph. In the present work we investigate some classes of graphs which admit prime labeling. We also introduce the concept of k-prime labeling and investigate some results concern to it. This work is a nice combination of graph theory and elementary number theory.