TITLE:
NK-Labeling of Graphs
AUTHORS:
Nasreen Almohanna, Khawlah Alhulwah
KEYWORDS:
Graph, Edge Coloring, NK-Labeling, Label, Path, Cycle, Wheel, Complete Graph
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.14 No.4,
October
21,
2024
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
)modn
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
χ
′
NK
(
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.