Nowhere-zero modular edge-graceful graphs

Ryan Jones; Ping Zhang

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 487-505
  • ISSN: 2083-5892

Abstract

top
For a connected graph G of order n ≥ 3, let f: E(G) → ℤₙ be an edge labeling of G. The vertex labeling f’: V(G) → ℤₙ induced by f is defined as f ' ( u ) = ∑ v ∈ N ( u ) f ( u v ) , where the sum is computed in ℤₙ. If f’ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A modular edge-graceful labeling f of G is nowhere-zero if f(e) ≠ 0 for all e ∈ E(G) and in this case, G is a nowhere-zero modular edge-graceful graph. It is shown that a connected graph G of order n ≥ 3 is nowhere-zero modular edge-graceful if and only if n ≢ 2 mod 4, G ≠ K₃ and G is not a star of even order. For a connected graph G of order n ≥ 3, the smallest integer k ≥ n for which there exists an edge labeling f: E(G) → ℤₖ - 0 such that the induced vertex labeling f’ is one-to-one is referred to as the nowhere-zero modular edge-gracefulness of G and this number is determined for every connected graph of order at least 3.

How to cite

top

Ryan Jones, and Ping Zhang. "Nowhere-zero modular edge-graceful graphs." Discussiones Mathematicae Graph Theory 32.3 (2012): 487-505. <http://eudml.org/doc/271066>.

@article{RyanJones2012,
abstract = {For a connected graph G of order n ≥ 3, let f: E(G) → ℤₙ be an edge labeling of G. The vertex labeling f’: V(G) → ℤₙ induced by f is defined as $f^\{\prime \}(u) = ∑_\{v ∈ N(u)\} f(uv)$, where the sum is computed in ℤₙ. If f’ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A modular edge-graceful labeling f of G is nowhere-zero if f(e) ≠ 0 for all e ∈ E(G) and in this case, G is a nowhere-zero modular edge-graceful graph. It is shown that a connected graph G of order n ≥ 3 is nowhere-zero modular edge-graceful if and only if n ≢ 2 mod 4, G ≠ K₃ and G is not a star of even order. For a connected graph G of order n ≥ 3, the smallest integer k ≥ n for which there exists an edge labeling f: E(G) → ℤₖ - 0 such that the induced vertex labeling f’ is one-to-one is referred to as the nowhere-zero modular edge-gracefulness of G and this number is determined for every connected graph of order at least 3.},
author = {Ryan Jones, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {modular edge-graceful labelings and graphs; nowhere-zero labelings; modular edge-gracefulness},
language = {eng},
number = {3},
pages = {487-505},
title = {Nowhere-zero modular edge-graceful graphs},
url = {http://eudml.org/doc/271066},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Ryan Jones
AU - Ping Zhang
TI - Nowhere-zero modular edge-graceful graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 487
EP - 505
AB - For a connected graph G of order n ≥ 3, let f: E(G) → ℤₙ be an edge labeling of G. The vertex labeling f’: V(G) → ℤₙ induced by f is defined as $f^{\prime }(u) = ∑_{v ∈ N(u)} f(uv)$, where the sum is computed in ℤₙ. If f’ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A modular edge-graceful labeling f of G is nowhere-zero if f(e) ≠ 0 for all e ∈ E(G) and in this case, G is a nowhere-zero modular edge-graceful graph. It is shown that a connected graph G of order n ≥ 3 is nowhere-zero modular edge-graceful if and only if n ≢ 2 mod 4, G ≠ K₃ and G is not a star of even order. For a connected graph G of order n ≥ 3, the smallest integer k ≥ n for which there exists an edge labeling f: E(G) → ℤₖ - 0 such that the induced vertex labeling f’ is one-to-one is referred to as the nowhere-zero modular edge-gracefulness of G and this number is determined for every connected graph of order at least 3.
LA - eng
KW - modular edge-graceful labelings and graphs; nowhere-zero labelings; modular edge-gracefulness
UR - http://eudml.org/doc/271066
ER -

References

top
  1. [1] L. Addario-Berry, R.E.L. Aldred, K. Dalal and B.A. Reed, Vertex colouring edge partitions, J. Combin. Theory (B) 94 (2005) 237-244, doi: 10.1016/j.jctb.2005.01.001. Zbl1074.05031
  2. [2] P.N. Balister, E. Györi, J. Lehel and R.H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math. 21 (2007) 237-250, doi: 10.1137/S0895480102414107. Zbl1189.05056
  3. [3] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs ( Fifth Edition, Chapman & Hall/CRC, Boca Raton, FL, 2010). Zbl1211.05001
  4. [4] G. Chartrand, F. Okamoto and P. Zhang, The sigma chromatic number of a graph, Graphs Combin. 26 (2010) 755-773, doi: 10.1007/s00373-010-0952-7. Zbl1207.05049
  5. [5] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman & Hall/CRC Press, Boca Raton, 2009). Zbl1169.05001
  6. [6] E. Györi, M. Horňák, C. Palmer and M. Woźniak, General neighbor-distinguishing index of a graph, Discrete Math. 308 (2008) 827-831, doi: 10.1016/j.disc.2007.07.046. Zbl1143.05028
  7. [7] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 16 (2009) #DS6. Zbl0953.05067
  8. [8] R.B. Gnana Jothi, Topics in Graph Theory, Ph.D. Thesis, Madurai (Kamaraj University, 1991). 
  9. [9] S.W. Golomb, How to number a graph, Graph Theory and Computing, (Academic Press, New York, 1972) 23-37. 
  10. [10] R. Jones, K. Kolasinski, F. Okamoto and P. Zhang, Modular neighbor-distinguishing edge colorings of graphs, J. Combin. Math. Combin. Comput. 76 (2011) 159-175. Zbl1233.05104
  11. [11] R. Jones, K. Kolasinski and P. Zhang, A proof of the modular edge-graceful trees conjecture, J. Combin. Math. Combin. Comput., to appear. Zbl1247.05207
  12. [12] S.P. Lo, On edge-graceful labelings of graphs, Congr. Numer. 50 (1985) 231-241. Zbl0597.05054
  13. [13] F. Okamoto, E. Salehi and P. Zhang, A checkerboard problem and modular colorings of graphs, Bull. Inst. Combin Appl. 58 (2010) 29-47. Zbl1200.05087
  14. [14] F. Okamoto, E. Salehi and P. Zhang, A solution to the checkerboard problem, Intern. J. Comput. Appl. Math. 5 (2010) 447-458. 
  15. [15] A. Rosa, On certain valuations of the vertices of a graph in: Theory of Graphs, Proc. Internat. Sympos. Rome, 1966 (Gordon and Breach, New York, 1967) 349-355. 
  16. [16] Z. Zhang, L. Liu and J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626, doi: 10.1016/S0893-9659(02)80015-5. Zbl1008.05050

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.