%0 Journal Article
%T <i>NK</i>-Labeling of Graphs
%A Nasreen Almohanna
%A Khawlah Alhulwah
%J American Journal of Computational Mathematics
%P 391-400
%@ 2161-1211
%D 2024
%I Scientific Research Publishing
%R 10.4236/ajcm.2024.144020
%X 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 <i>G</i>'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 <i>NK</i>-labeling. Let <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>c</mi><mo>:</mo><mi>E</mi><mrow><mo>(</mo>
   <mi>G</mi>
  <mo>)</mo></mrow><mo>&#x2192;</mo><mi>&#x2115;</mi></mrow>
</math>

 be a proper edge coloring of <i>G</i> which induces a proper vertex coloring <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msup>
   <mi>c</mi>
   <mo>&#x2032;</mo>
  </msup>
  <mo>:</mo><mi>V</mi><mrow><mo>(</mo>
   <mi>G</mi>
  <mo>)</mo></mrow><mo>&#x2192;</mo><msub>
   <mi>&#x2124;</mi>
   <mi>n</mi>
  </msub>
  </mrow>
</math>

 defined by <math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msup>
   <mi>c</mi>
   <mo>&#x2032;</mo>
  </msup>
  <mrow><mo>(</mo>
   <mi>v</mi>
  <mo>)</mo></mrow><mo>&#x2261;</mo><munder>
   <mstyle mathsize='140%' displaystyle='true'><mo>&#x2211;</mo></mstyle>
   <mrow>
    <mi>e</mi><mo>&#x2208;</mo><msub>
     <mi>E</mi>
     <mi>v</mi>
    </msub>
    </mrow>
  </munder>
  <mtext>&#x2009;</mtext><mi>c</mi><mrow><mo>(</mo>
   <mi>e</mi>
  <mo>)</mo></mrow><mi>mod</mi><mi>n</mi></mrow>
</math>

 Such that <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>E</mi>
   <mi>v</mi>
  </msub>
  </mrow>
</math>

 is the set of edges incident with <math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mi>v</mi>
</math>

 in <i>G</i>. The minimum positive integer for which the graph <i>G</i> has <i>NK</i>-labeling called <i>NK</i>-chromatic index and denoted by <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <msup>
    <mi>&#x03C7;</mi>
    <mo>&#x2032;</mo>
   </msup>
   
   <mrow>
    <mi>N</mi><mi>K</mi></mrow>
  </msub>
  <mrow><mo>(</mo>
   <mi>G</mi>
  <mo>)</mo></mrow></mrow>
</math>

. We study the <i>NK</i>-labeling of several well-known classes of graphs. It is shown that the <i>NK</i>-chromatic of the path <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>P</mi>
   <mi>n</mi>
  </msub>
  </mrow>
</math>

 for <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>n</mi><mo>&#x2265;</mo><mn>4</mn></mrow>
</math>

 is three and for odd <math display='inline'
%K Graph
%K Edge Coloring
%K <i>NK</i>-Labeling
%K Label
%K Path
%K Cycle
%K Wheel
%K Complete Graph
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=136708