NK -Labeling of Graphs

Abstract

A graph labeling is the assigning of labels to the vertices, edges, or both (usually non-negative integers), often satisfying some prescribed requirements. This terminology has become standard. A graph G 's edges can be colored by assigning a different color to each of its edges. The edge coloring is appropriate if adjacent edges are given different colors. In this work, we introduce a new labeling called NK -labeling. Let c : E ( G ) → ℕ be a proper edge coloring of G which induces a proper vertex coloring c ′ : V ( G ) → ℤ n defined by c ′ ( v ) ≡ ∑ e ∈ E v c ( e ) mod n Such that E v is the set of edges incident with v in G . The minimum positive integer for which the graph G has NK -labeling called NK -chromatic index and denoted by χ ′ N K ( G ) . We study the NK -labeling of several well-known classes of graphs. It is shown that the NK -chromatic of the path P n for n ≥ 4 is three and for odd n , the NK -chromatic of the complete graph K n is n . Other results dealing with the NK -labeling are also presented.