Nasreen Almohanna, Khawlah Alhulwah
Department of Mathematics and Statistics, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, Saudi Arabia.
DOI: 10.4236/ajcm.2024.144020   PDF    HTML   XML   180 Downloads   1,029 Views   Citations

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\left(G\right)\to \mathbb{N}$ be a proper edge coloring of G which induces a proper vertex coloring $c^{\prime }:V\left(G\right)\to {\mathbb{Z}}_n$ defined by $c^{\prime }\left(v\right)\equiv {\displaystyle \sum }_{e\in E_v}c\left(e\right)\mathrm{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 ${{\chi }^{\prime }}_{NK}\left(G\right)$ . 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\ge 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.

Keywords

Graph, Edge Coloring, NK-Labeling, Label, Path, Cycle, Wheel, Complete Graph

Share and Cite:

1. Introduction

For terms and symbols related to graph theory that are not covered in this paper, please see the book [1]. In 1968, Alexander Rosa received his Ph.D from Slovak Academy of Science under Anton Kotzig after he published his paper titled “On certain valuations of the vertices of a graph,” which is the source of many labelings. The most attention of his labeling is β -valuation, which recalled a graceful labeling by Solomon W. Golomb [2]. Graph coloring is one of the most useful models in graph theory. Many problems relating to computer registers allocation, electronic bandwidth allocation, and school scheduling have all been resolved using it.

Let G be a graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$ . A labeling $c:E\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ such that $c\left(e\right)\ne c\left(f\right)$ for every two adjacent edges e and $f$ in G is called proper edge coloring.

We frequently have an interest in proper edge coloring that use a minimum number of colors which called chromatic index (edge chromatic number) ${\chi }^{\prime }\left(G\right)$ of a graph G. A graph G is k-colorable, if ${\chi }^{\prime }\left(G\right)\le k$ , and G is k-chromatic, if ${\chi }^{\prime }\left(G\right)=k$ .

Maheo and Sacle in [3] studied the irregular-sum chromatic index for connected graph G with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$ of order $n\ge 3$ . A proper edge coloring $c:E\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ for some integer $k\ge 2$ is called an irregular-sum chromatic coloring of G if the induced vertex coloring $c^{\prime }:V\left(G\right)\to \mathbb{N}$ defined by$c^{\prime }\left(v\right)={\displaystyle \sum }_{e\in E_v}c\left(e\right)$ is irregular (vertex-distinguishing). The minimum positive integer for which G has such an irregular-sum chromatic coloring is called an irregular-sum chromatic index of G and is denoted by ${{\chi }^{\prime }}_{is}\left(G\right)$ .

In [4] [5], Ping Zhang introduced the labeling for a graph G of order $n$ . Let $c:E\left(G\right)\to {\mathbb{Z}}_k$ , $k\ge n$ be an unrestricted edge coloring (where the adjacent edges may be colored the same). The edge coloring c induces a vertex coloring $c^{\prime }:V\left(G\right)\to {\mathbb{Z}}_k$ defined by$c^{\prime }\left(v\right)={\displaystyle \sum }_{e\in E_v}c\left(e\right)$ where the sum is computed in ${\mathbb{Z}}_k$ . For some positive integer $k$ , such an edge coloring c is always present. The modular edge-gracefulness $meg\left(G\right)$ of G is the minimum $k$ for which such a vertex-distinguishing edge coloring of G exists. Thus, $meg\left(G\right)\ge n$ for every connected graph G of order $n\ge 3$ . If $meg\left(G\right)=n$ , then G is called a modular edge-graceful graph and a vertex-distinguishing edge coloring $c:E\left(G\right)\to {\mathbb{Z}}_n$ is called a modular edge-graceful labeling as well as a modular edge-graceful coloring of G.

Based on established graph coloring ideas and inspired by irregular-sum and modular edge-graceful labeling we present a new concept for coloring graphs focusing on proper coloring in this paper.

Let $\mathbb{N}$ be the set of all positive integers and let $E_v$ denoted the set of edges incident with $v$ in G. For a connected simple graph $G\left(V,E\right)$ of order $n\ge 3$ , A proper edge coloring $c:E\left(G\right)\to \mathbb{N}$ induces a proper vertex coloring $c^{\prime }:V\left(G\right)\to {\mathbb{Z}}_n$ , defined by$c^{\prime }\left(v\right)\equiv {\displaystyle \sum }_{e\in E_v}c\left(e\right)\mathrm{mod}n$

The minimum positive integer for which G has NK-labeling is called NK-chromatic index and denoted by ${{\chi }^{\prime }}_{NK}\left(G\right)$ . A graph G with chromatic number ${{\chi }^{\prime }}_{NK}\left(G\right)\le k$ is called a k-NKcolorable graph. If no such k, the graph G is not NK-colorable.

2. Preliminaries

Proposition 2.1 For any connected graph G$\text{Δ}\left(G\right)\le {\chi }^{\prime }\left(G\right)\le {{\chi }^{\prime }}_{NK}\left(G\right)$ where $\text{Δ}\left(G\right)$ is the maximum degree of G.

Proposition 2.2 If G is a connected graph of order at least 3 such that G contains two adjacent vertices of maximum degree, then ${{\chi }^{\prime }}_{NK}\left(G\right)\ge \Delta \left(G\right)+1$ .

An illustration of the NK-chromatic index. We show in Figure 1, ${{\chi }^{\prime }}_{NK}\left(G\right)\le 4$ and from preposition 2.2, ${{\chi }^{\prime }}_{NK}\left(G\right)\ge 4$ . Hence, ${{\chi }^{\prime }}_{NK}\left(G\right)=4$ .

Figure 1. An illustration of NK-labeling.

3. Well Known Classes of Graphs

We now turn our attention to two other well-known classes of graphs, namely path and cycles.

Theorem 3.1 Let n be an integer greater than 4, the NK-chromatic index of the path $P_n$ of order n is three.

Proof. By preposition 2.2, ${{\chi }^{\prime }}_{NK}\left(P_n\right)\ge 3$ . To prove ${{\chi }^{\prime }}_{NK}\left(P_n\right)\le 3$ , for $1\le i\le n-1$ , assign the edge $v_i{v}_{i+1}$ by a color c as following.

$c\left(v_i{v}_{i+1}\right)=\{\begin{array}{ll}1\hfill & \text{if}i\equiv 1\mathrm{mod}3\hfill \\ 2\hfill & \text{if}i\equiv 2\mathrm{mod}3\hfill \\ 3\hfill & \text{if}i\equiv 0\mathrm{mod}3\hfill \end{array}$

Case 1: $n\equiv 0\mathrm{mod}3$ , the previous edge color induces the following proper vertex coloring for $v_j,1\le j\le n$ given by$c^{\prime }\left(v_j\right)=\{\begin{array}{ll}1\hfill & \text{if}j=1\hfill \\ 2\hfill & \text{if}j=n\hfill \\ 3\hfill & \text{if}j\equiv 2\mathrm{mod}3\hfill \\ 4\hfill & \text{if}j\equiv 1\mathrm{mod}3,j\ne 1\hfill \\ 5\hfill & \text{if}j\equiv 0\mathrm{mod}3,j\ne n\hfill \end{array}$

Hence, ${\chi }_{NK}\left(P_n\right)=3$ .

Case 2: $n\equiv 1\mathrm{mod}3$ . For $n=4$ , we show the NK-labeling of $P_4$ in Figure 2, so ${{\chi }^{\prime }}_{NK}\left(P_4\right)=3$ .

Figure 2. NK-labeling of P₄.

For $n\ge 7$ , the previous edge color induces the following proper vertex coloring for $v_j,1\le j\le n$ given by$c^{\prime }\left(v_j\right)=\{\begin{array}{ll}1\hfill & \text{if}j=1\hfill \\ 3\hfill & \text{if}j\equiv 2\mathrm{mod}3,j=n\hfill \\ 4\hfill & \text{if}j\equiv 1\mathrm{mod}3,j\ne 1,n\hfill \\ 5\hfill & \text{if}j\equiv 0\mathrm{mod}3\hfill \end{array}$

Hence, ${{\chi }^{\prime }}_{NK}\left(P_n\right)=3$ .

Case 3: $n\equiv 2\mathrm{mod}3$ . For $n=5$ , we show the NK-labeling of $P_5$ in Figure 3, so ${{\chi }^{\prime }}_{NK}\left(P_5\right)=3$ .

Figure 3. NK-labeling of P₅.

For $n\ge 8$ , the previous edge color induces the following proper vertex coloring for $v_j,1\le j\le n$ given by$c^{\prime }\left(v_j\right)=\{\begin{array}{ll}1\hfill & \text{if}j=1,n\hfill \\ 3\hfill & \text{if}j\equiv 2\mathrm{mod}3,j\ne n\hfill \\ 4\hfill & \text{if}j\equiv 1\mathrm{mod}3,j\ne 1\hfill \\ 5\hfill & \text{if}j\equiv 0\mathrm{mod}3\hfill \end{array}$

Hence, ${{\chi }^{\prime }}_{NK}\left(P_5\right)=3$ . Therefore, for $n\ge 4$ the NK-chromatic index of $P_n$ is 3.

Theorem 3.2 Let n be an integer greater than 3, the NK-chromatic index of the cycle $C_n$ of order n is${{\chi }^{\prime }}_{NK}\left(C_n\right)=\{\begin{array}{ll}3\hfill & \text{if}n\equiv 0\mathrm{mod}3\hfill \\ 4\hfill & \text{if}n\equiv 1\mathrm{mod}3\hfill \\ 5\hfill & \text{if}n\equiv 2\mathrm{mod}3\hfill \end{array}$

Proof. Case 1: $n\equiv 0\mathrm{mod}3$ .

Trivially we can show that ${{\chi }^{\prime }}_{NK}\left(C_3\right)=3$ . Now consider the cycle $C_n=\left(v_1,v_2,\cdots ,v_n,v_1\right)$ . Clearly, $3\le {{\chi }^{\prime }}_{NK}\left(C_n\right)$ by using the Proposition 2.2. We want to prove that ${{\chi }^{\prime }}_{NK}\left(C_n\right)\le 3$ . For $1\le i\le n-1$ , the edge $v_i{v}_{i+1}$ assigned by a color c as following

$c\left(v_i{v}_{i+1}\right)=\{\begin{array}{ll}1\hfill & \text{if}i\equiv 1\mathrm{mod}3\hfill \\ 2\hfill & \text{if}i\equiv 2\mathrm{mod}3\hfill \\ 3\hfill & \text{if}i\equiv 0\mathrm{mod}3\hfill \end{array}c\left(v_n{v}_1\right)=3$

So, we get a proper vertex coloring as following, for $1\le j\le n$ ,$c^{\prime }\left(v_j\right)=\{\begin{array}{ll}3\hfill & \text{if}n\equiv 2\mathrm{mod}3\hfill \\ 4\hfill & \text{if}n\equiv 1\mathrm{mod}3\hfill \\ 5\hfill & \text{if}n\equiv 0\mathrm{mod}3\hfill \end{array}$

Therefore, ${{\chi }^{\prime }}_{NK}\left(C_n\right)=3$ .

Case 2: $n\equiv 1\mathrm{mod}3$

Clearly for any three consecutive edges in $C_n$ , they cannot color by i, j, i, otherwise we get improper vertex coloring. Hence we start to color $v_1{v}_2$ by 1, $v_2{v}_3$ by 2, $v_3{v}_4$ by 3, $v_4{v}_5$ by 1, $v_5{v}_6$ by 2 and so on. Since $n\equiv 1\mathrm{mod}3$ , we end with $c\left(v_{n-1}{v}_n\right)=3$ . Then we need a new color 4 for the edge $v_n{v}_1$ , otherwise we get improper vertex coloring. Therefore ${{\chi }^{\prime }}_{NK}\left(C_n\right)\ge 4$ .

To prove that ${{\chi }^{\prime }}_{NK}\left(C_n\right)\le 4$ , for $C_4$ we show in Figure 4, ${{\chi }^{\prime }}_{NK}\left(C_4\right)\le 4$ .

Figure 4. NK-labeling of C₄.

For $n\ge 7$ , for $1\le i\le n-1$ , we did as case 1 with$c\left(v_i{v}_{i+1}\right)=\{\begin{array}{ll}1\hfill & \text{if}i\equiv 1\mathrm{mod}3\hfill \\ 2\hfill & \text{if}i\equiv 2\mathrm{mod}3\hfill \\ 3\hfill & \text{if}i\equiv 0\mathrm{mod}3\hfill \end{array}c\left(v_n{v}_1\right)=4$

Then we get a proper vertex coloring as following, for $1\le j\le n$ ,$c^{\prime }\left(v_j\right)=\{\begin{array}{ll}3\hfill & \text{if}j\equiv 2\mathrm{mod}3\hfill \\ 4\hfill & \text{if}j\equiv 1\mathrm{mod}3,j\ne 1,n\hfill \\ 5\hfill & \text{if}j\equiv 0\mathrm{mod}3,j=1\hfill \\ 7\mathrm{mod}n\hfill & \text{if}j=n\hfill \end{array}$

Hence, ${{\chi }^{\prime }}_{NK}\left(C_n\right)=4$ .

Case 3: $n\equiv 2\mathrm{mod}3$ .

We start to color $v_1{v}_2$ by 1, $v_2{v}_3$ by 2, $v_3{v}_4$ by 3, $v_4{v}_5$ by 1, $v_5{v}_6$ by 2 and so on. Since $n\equiv 2\mathrm{mod}3$ , we end with $c\left(v_{n-2}{v}_{n-1}\right)=3$ . For the edges $v_{n-1}{v}_n$ and $v_n{v}_1$ we have to use new colors 4, 5 respectively, otherwise we get improper vertex coloring. Hence ${{\chi }^{\prime }}_{NK}\left(C_n\right)\ge 5$ . To show ${{\chi }^{\prime }}_{NK}\left(C_n\right)\le 5$ . For $C_5$ , we show in Figure 5, ${{\chi }^{\prime }}_{NK}\left(C_5\right)\le 5$ .

Figure 5. NK-labeling of C₅.

For $n\ge 8$ , for $1\le i\le n-1$ ,$c\left(v_i{v}_{i+1}\right)=\{\begin{array}{ll}1\hfill & \text{if}i\equiv 1\mathrm{mod}3,i\ne n-1\hfill \\ 2\hfill & \text{if}i\equiv 2\mathrm{mod}3\hfill \\ 3\hfill & \text{if}i\equiv 0\mathrm{mod}3\hfill \\ 4\hfill & \text{if}i=n-1\hfill \end{array}c\left(v_n{v}_1\right)=5$

Then we get a proper vertex coloring as following, for $1\le j\le n$ ,$c^{\prime }\left(v_j\right)=\{\begin{array}{ll}3\hfill & \text{if}j\equiv 2\mathrm{mod}3,j\ne n\hfill \\ 4\hfill & \text{if}j\equiv 1\mathrm{mod}3,j\ne 1,n-1\hfill \\ 5\hfill & \text{if}j\equiv 0\mathrm{mod}3,j=1\hfill \\ 6\hfill & \text{if}j=1\hfill \\ 7\hfill & \text{if}j=n-1\hfill \\ 9\mathrm{mod}n\hfill & \text{if}j=n\hfill \end{array}$

Now we will focus on some well-known classes of graph with odd order.

Theorem 3.3 Let S be a star of odd order $n\ge 3$ , the NK-chromatic index of S is $n-1$ .

Proof. Let $V\left(S\right)=\left\{v,v_1,v_2,\cdots ,v_{n-1}\right\}$ where $\text{deg}\left(v\right)=n-1$ , $\text{deg}\left(v_i\right)=1$ , $1\le i\le n-1$ . Color the edge $v{v}_i$ by $i$ , which induces a proper vertex coloring$c^{\prime }\left(v_i\right)=i\text{and}{c}^{\prime }\left(v\right)\equiv {\displaystyle \sum }_{i=1}^{n-1}i\mathrm{mod}n\equiv \frac{\left(n-1\right)n}{2}\mathrm{mod}n\equiv 0\mathrm{mod}n$

Hence, ${{\chi }^{\prime }}_{NK}\left(S\right)\le n-1$ . Moreover, by preposition 2.1, we have ${{\chi }^{\prime }}_{NK}\left(S\right)\ge n-1$ because ${\chi }^{\prime }\left(S\right)=n-1$ .

Theorem 3.4 For odd integer $n$ . Let $W_n$ be a wheel of order $n\ge 5$ , the NK-chromatic index of $W_n$ is $n-1$

Proof. Let $V\left(W_n\right)=\left\{v,v_1,v_2,\cdots ,v_{n-1}\right\}$ where $\text{deg}\left(v\right)=n-1$ , $\text{deg}\left(v_i\right)=3$ , $1\le i\le n-1$ . By proposition 2.1, $n-1\le {{\chi }^{\prime }}_{NK}\left(W_n\right)$ . It is reminded to prove that ${{\chi }^{\prime }}_{NK}\left(W_n\right)\le n-1$ .

Case 1: $n\cancel{\equiv }0\mathrm{mod}3$ . Assign the colors of the edge e as following$c\left(e\right)=\{\begin{array}{ll}1\hfill & \text{for}e=v_{n-2}{v}_{n-1}\hfill \\ 2\hfill & \text{for}e=v_{n-1}{v}_1\hfill \\ i\hfill & \text{for}e=v{v}_i\hfill \\ i+2\hfill & \text{for}e=v_j{v}_{j+1},1\le j\le n-3\hfill \end{array}$

We get three types of 3-cycle

1-$C_3=\left(v,v_i,v_{i+1},v\right)$ , $1\le i\le n-3$ ,

2-${C^{\prime }}_3=\left(v,v_{n-2},v_{n-1},v\right)$ ,

3-${C^{″}}_3=\left(v,v_{n-1},v_1,v\right)$ ,

First, suppose that there exist two vertices of $C_3$ have same color. Thus $c^{\prime }\left(v_i\right)=c^{\prime }\left(v_{i+1}\right)$ or $c^{\prime }\left(v\right)=c^{\prime }\left(v_i\right)$ . Assume that$c^{\prime }\left(v_i\right)=c^{\prime }\left(v_{i+1}\right)$ $i+\left(i+1\right)+\left(i+2\right)-k_{1}n=\left(i+1\right)+\left(i+2\right)+\left(i+3\right)-k_{2}n{k}_1,k_2\text{are integers}$ $3\left(i+2\right)-3\left(i+1\right)=k_{2}n-k_{1}n$ $3=\left(k_2-k_1\right)n$

Which impossible since $n\ge 5$ . So, we may assume that$c^{\prime }\left(v\right)=c^{\prime }\left(v_i\right)$ $0-k_{1}n=i+\left(i+1\right)+\left(i+2\right)-k_{2}n{k}_1,k_2\text{are integers}$ $3\left(i+1\right)=\left(k_2-k_1\right)n$

Since 3 is prime, 3 divides $k_2-k_1$ which implies that $i+1$ is a multiple of n, contradiction. Hence $C_3=\left(v,v_i,v_{i+1},v\right)$ , $1\le i\le n-3$ has proper vertex-coloring. Moreover, according on the edge coloring $c^{\prime }\left(v_{n-2}\right)=n-2$ , $c^{\prime }\left(v_{n-1}\right)=2$ , $c^{\prime }\left(v_1\right)=6\mathrm{mod}n$ . Thus, ${C^{\prime }}_3$ and ${C^{″}}_3$ have a proper vertex-coloring. This implies ${{\chi }^{\prime }}_{NK}\left(W_n\right)\le n-1$ .

Next, if $n\equiv 0\mathrm{mod}3$ , then assign the colors of the edge e as following

$c\left(e\right)=\{\begin{array}{ll}1\hfill & \text{for}e=v_{n-3}{v}_{n-2}\hfill \\ 2\hfill & \text{for}e=v_{n-2}{v}_{n-1}\hfill \\ 3\hfill & \text{for}e=v_{n-1}{v}_1\hfill \\ i\hfill & \text{for}e=v{v}_i\hfill \\ i+3\hfill & \text{for}e=v_j{v}_{j+1},1\le j\le n-4\hfill \end{array}$

We get four types of 3-cycle

1-$C_3=\left(v,v_i,v_{i+1},v\right)$ , $1\le i\le n-4$ ,

2-${C^{\prime }}_3=\left(v,v_{n-3},v_{n-2},v\right)$ ,

3-${C^{″}}_3=\left(v,v_{n-2},v_{n-1},v\right)$ ,

4-${C^{‴}}_3=\left(v,v_{n-1},v_1,v\right)$ ,

As above we can prove that $C_3$ has proper vertex coloring. First, suppose that there exist two vertices of $C_3$ have same color. Thus $c^{\prime }\left(v_i\right)=c^{\prime }\left(v_{i+1}\right)$ or $c^{\prime }\left(v\right)=c^{\prime }\left(v_i\right)$ . Assume that$c^{\prime }\left(v_i\right)=c^{\prime }\left(v_{i+1}\right)$ $i+\left(i+2\right)+\left(i+3\right)-k_{1}n=\left(i+1\right)+\left(i+3\right)+\left(i+4\right)-k_{2}n{k}_1,k_2\text{are integers}$ $3=\left(k_1-k_2\right)n$

Which impossible since $n\ge 9$ . So, we may assume that$c^{\prime }\left(v\right)=c^{\prime }\left(v_i\right)$ $0-k_{1}n=i+\left(i+2\right)+\left(i+3\right)-k_{2}n{k}_1,k_2\text{are integers}$ $5+3i=\left(k_1-k_2\right)n$

Since $n\equiv 0\mathrm{mod}3$ , there is integer k such that $n=3k$ so$5+3i=3\left(k_1-k_2\right)k$

which implies that 5 is a multiple of 3, contradiction. Hence $C_3=\left(v,v_i,v_{i+1},,v\right),1\le i\le n-3$ has proper vertex-coloring. Moreover, according to the edge coloring $c^{\prime }\left(v_{n-3}\right)=n-3$ , $c^{\prime }\left(v_{n-2}\right)=1$ , $c^{\prime }\left(v_{n-1}\right)=4$ and $c^{\prime }\left(v_1\right)=8\mathrm{mod}n$ .Thus ${C^{\prime }}_3$ , ${C^{″}}_3$ and ${C^{‴}}_3$ have proper vertex coloring. Hence, ${{\chi }^{\prime }}_{NK}\left(W_n\right)=n-1$ .

Theorem 3.5 For odd integer $n$ , the NK-chromatic index of the complete graph $K_n$ is n.

Proof. The graph $K_n$ is $\left(n-1\right)$ -regular graph with size $\frac{n\left(n-1\right)}{2}$ . Moreover, for odd order n, ${\chi }^{\prime }\left(K_n\right)=n$ . From Proposition 2.1, $n\le {{\chi }^{\prime }}_{NK}\left(K_n\right)$ . We will color the edges of $K_n$ by proper edge coloring using this n colors. Therefore, every vertex in $K_n$ incident with $n-1$ different colors. We will denote the vertex that incident with the colors $V_i=\left\{1,2,3,i-1,i+1,n\right\}$ by $v_i,1\le i\le n$ . Each color $i$ belong to all $V_j$ such that $i\ne j$ , otherwise $deg\left(v_i\right)<n-1$ . Since $i\notin V_i$ and from the definition of NK-labeling, $c^{\prime }\left(v_i\right)={\displaystyle {\sum }_{j=1}^{n}j}-i=n-i$ . It is clear that for $i\ne j$ , $c^{\prime }\left(v_i\right)\ne c^{\prime }\left(v_j\right)$ .

An example of odd complete graph, Figure 6 illustrate ${{\chi }^{\prime }}_{NK}\left(K_7\right)\le 7$ so NK-chromatic index of $K_7$ is 7.

Figure 6. The NK-labeling of K₇.

Proposition 3.6 If G is a graph of size $m\ge 1$ , then${{\chi }^{\prime }}_{NK}\left(G\right)\ge \frac{m}{{\alpha }^{\prime }\left(G\right)}$ where ${\alpha }^{\prime }\left(G\right)$ is the maximum number of edges in an independent set of edges of a graph G.

Proof. Suppose that ${{\chi }^{\prime }}_{NK}\left(G\right)=k$ and that $E_1,E_2,\cdots ,E_k$ are the edge color classes in k-edge coloring of G. Thus $\left|E_i\right|\le {\alpha }^{\prime }\left(G\right)$ for each $i$ ($1\le i\le k$ ). Moreover, from the definition of NK-labeling, it is clear that ${\chi }^{\prime }\left(G\right)\le {{\chi }^{\prime }}_{NK}\left(G\right)$ . Therefore if $F_1,F_2,\cdots ,F_l$ , $l\ge k$ are the color classes of ${{\chi }^{\prime }}_{NK}\left(G\right)$ such that ${{\chi }^{\prime }}_{NK}\left(G\right)=l$ , then $\left|F_j|\le |E_i\right|\le {\alpha }^{\prime }\left(G\right)$ for all $i,j$ . Hence $m=\left|E\left(G\right)\right|={\displaystyle {\sum }_{j=1}^l\left|F_j\right|}\le {{\chi }^{\prime }}_{NK}\left(G\right)\cdot {\alpha }^{\prime }\left(G\right)$ .

Some of the complete graphs $K_{2n}$ , $n\ge 3$ are NK-colorable, ${{\chi }^{\prime }}_{NK}\left(K_4\right)=5$ . From Figure 7, ${{\chi }^{\prime }}_{NK}\left(G\right)\le 5$ . Now, suppose that $K_4$ can be color by using 4 colors. We may assume that $c\left(v_1{v}_2\right)=1$ in Figure 2. Since c is a proper edge coloring, none of the edges $v_1{v}_3$ , $v_2{v}_4$ , $v_2{v}_3$ and $v_1{v}_4$ can be colored by the color 1. Hence two of these four edges must be assigned the same color and the remaining two edges must be assigned different colors, otherwise $c^{\prime }\left(v_1\right)=c^{\prime }\left(v_2\right)$ which is impossible. Assume $c\left(v_1{v}_3\right)=c\left(v_2{v}_4\right)=2$ , $c\left(v_2{v}_3\right)=3$ and $c\left(v_1{v}_4\right)=4$ . The last edge should be colored by the color 1, but in this case $c^{\prime }\left(v_2\right)=c^{\prime }\left(v_3\right)$ , contradiction. Therefore ${{\chi }^{\prime }}_{NK}\left(K_4\right)\ge 5$ . Hence, ${{\chi }^{\prime }}_{NK}\left(K_4\right)=5$ .

Figure 7. The NK-labeling of K₄.

Problem: For even integer $n$ , determine the NK-chromatic index of the complete graph $K_n$ if it exists.

4. Conclusion

Graph labeling is one of the main topics of graph theory, and it is used in a variety of fields, such as coding theory, X-ray crystallography, radar, astronomy, circuit design, communication network addressing, and database management. In this article, we introduced a new concept of graph labeling and found the NK-labeling of special graphs such as path, cycle, wheel, star, and complete graph for some n. Furthermore, we find the lower bound of our labeling.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Chartrand, G., Lesniak, L. and Zhang, P. (2010) Graphs and Digraphs. 5th Edition, Chapman and Hall/CRC.[CrossRef]
[2]	Golomb, S. (1972) How to Number a Graph. Graph Theory and Computing, 23-27.[CrossRef]
[3]	Mahéo, M. and Saclé, J.F. (2008) Some Results in (∑,p,g)-Valuation of Connected Graphs. Report de Recherche 1497. Universte' de Paris-Sud, Center d'Orsay.
[4]	Zhang, P. (2015) Color-Induced Graph Colorings. Springer.[CrossRef]
[5]	Zhang, P. (2015) A Kaleidoscopic View of Graph Colorings. Springer.[CrossRef]