A magical approach to some labeling conjectures

Ramon M. Figueroa-Centeno; Rikio Ichishima; Francesc A. Muntaner-Batle; Akito Oshima

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 1, page 79-113
  • ISSN: 2083-5892

Abstract

top
In this paper, a complete characterization of the (super) edge-magic linear forests with two components is provided. In the process of establishing this characterization, the super edge-magic, harmonious, sequential and felicitous properties of certain 2-regular graphs are investigated, and several results on super edge-magic and felicitous labelings of unions of cycles and paths are presented. These labelings resolve one conjecture on harmonious graphs as a corollary, and make headway towards the resolution of others. They also provide the basis for some new conjectures (and a weaker form of an old one) on labelings of 2-regular graphs.

How to cite

top

Ramon M. Figueroa-Centeno, et al. "A magical approach to some labeling conjectures." Discussiones Mathematicae Graph Theory 31.1 (2011): 79-113. <http://eudml.org/doc/270995>.

@article{RamonM2011,
abstract = {In this paper, a complete characterization of the (super) edge-magic linear forests with two components is provided. In the process of establishing this characterization, the super edge-magic, harmonious, sequential and felicitous properties of certain 2-regular graphs are investigated, and several results on super edge-magic and felicitous labelings of unions of cycles and paths are presented. These labelings resolve one conjecture on harmonious graphs as a corollary, and make headway towards the resolution of others. They also provide the basis for some new conjectures (and a weaker form of an old one) on labelings of 2-regular graphs.},
author = {Ramon M. Figueroa-Centeno, Rikio Ichishima, Francesc A. Muntaner-Batle, Akito Oshima},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge-magic labelling; edge-magic total labelling; felicitous labelling; harmonious labelling; sequential labelling},
language = {eng},
number = {1},
pages = {79-113},
title = {A magical approach to some labeling conjectures},
url = {http://eudml.org/doc/270995},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Ramon M. Figueroa-Centeno
AU - Rikio Ichishima
AU - Francesc A. Muntaner-Batle
AU - Akito Oshima
TI - A magical approach to some labeling conjectures
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 1
SP - 79
EP - 113
AB - In this paper, a complete characterization of the (super) edge-magic linear forests with two components is provided. In the process of establishing this characterization, the super edge-magic, harmonious, sequential and felicitous properties of certain 2-regular graphs are investigated, and several results on super edge-magic and felicitous labelings of unions of cycles and paths are presented. These labelings resolve one conjecture on harmonious graphs as a corollary, and make headway towards the resolution of others. They also provide the basis for some new conjectures (and a weaker form of an old one) on labelings of 2-regular graphs.
LA - eng
KW - edge-magic labelling; edge-magic total labelling; felicitous labelling; harmonious labelling; sequential labelling
UR - http://eudml.org/doc/270995
ER -

References

top
  1. [1] J. Abrham and A. Kotzig, Graceful valuations of 2-regular graphs with two components, Discrete Math. 150 (1996) 3-15, doi: 10.1016/0012-365X(95)00171-R. Zbl0856.05086
  2. [2] G. Chartrand and L. Lesniak, Graphs and Digraphs (Wadsworth & Brook/Cole Advanced Books and Software, Monterey, Calif. 1986). Zbl0666.05001
  3. [3] H. Enomoto, A. Lladó, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998) 105-109. Zbl0918.05090
  4. [4] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math. 231 (2001) 153-168, doi: 10.1016/S0012-365X(00)00314-9. Zbl0977.05120
  5. [5] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On super edge-magic graphs, Ars Combin. 64 (2002) 81-96. Zbl1071.05568
  6. [6] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, Labeling the vertex amalgamation of graphs, Discuss. Math. Graph Theory 23 (2003) 129-139, doi: 10.7151/dmgt.1190. Zbl1054.05087
  7. [7] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On edge-magic labelings of certain disjoint unions of graphs, Austral. J. Combin. 32 (2005) 225-242. Zbl1070.05075
  8. [8] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On the super edge-magic deficiency of graphs, Ars Combin. 78 (2006) 33-45. Zbl1164.05445
  9. [9] R.M. Figueroa-Centeno, R. Ichishima, F.A. Muntaner-Batle and M. Rius-Font, Labeling generating matrices, J. Combin. Math. Combin. Comput. 67 (2008) 189-216. 
  10. [10] R. Frucht and L.C. Salinas, Graceful numbering of snakes with constraints on the first label, Ars Combin. (B) 20 (1985) 143-157. Zbl0594.05057
  11. [11] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (2009) #DS6. Zbl0953.05067
  12. [12] S.W. Golomb, How to number a graph, in: Graph Theory and Computing, R.C. Read, ed. (Academic Press, New York, 1972) 23-37. Zbl0293.05150
  13. [13] T. Grace, On sequential labelings of graphs, J. Graph Theory 7 (1983) 195-201, doi: 10.1002/jgt.3190070208. Zbl0522.05063
  14. [14] R.L. Graham and N.J. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Meth. 1 (1980) 382-404, doi: 10.1137/0601045. Zbl0499.05049
  15. [15] I. Gray and J.A. MacDougall, Vertex-magic labelings of regular graphs II, Discrete Math. 309 (2009) 5986-5999, doi: 10.1016/j.disc.2009.04.031. Zbl1226.05214
  16. [16] J. Holden, D. McQuillan and J.M. McQuillan, A conjecture on strong magic labelings of 2-regular graphs, Discrete Math. 309 (2009) 4130-4136, doi: 10.1016/j.disc.2008.12.020. Zbl1228.05314
  17. [17] A. Kotzig, β-valuations of quadratic graphs with isomorphic components, Utilitas Math. 7 (1975) 263-279. 
  18. [18] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull. 13 (1970) 451-461, doi: 10.4153/CMB-1970-084-1. Zbl0213.26203
  19. [19] S.M. Lee, E. Schmeichel and S.C. Shee, On felicitous graphs, Discrete Math. 93 (1991) 201-209, doi: 10.1016/0012-365X(91)90256-2. Zbl0741.05059
  20. [20] M. Seoud, A.E.I. Abdel Maqsoud and J. Sheehan, Harmonious graphs, Utilitas Math. 47 (1995) 225-233. Zbl0830.05055
  21. [21] S.C. Shee, On harmonious and related graphs, Ars Combin. 23 (1987) 237-247. Zbl0616.05055
  22. [22] S.C. Shee and S.M. Lee, On harmonious and felicitous labelings of graphs, Congress Numer. 68 (1989) 155-170. Zbl0689.05045
  23. [23] G. Ringel and A. Lladó, Another tree conjecture, Bull. Inst. Combin. Appl. 18 (1996) 83-85. 
  24. [24] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N.Y and Dunod Paris (1967) 349-355. 
  25. [25] W.D. Wallis, Magic Graphs (Birkhäuser, Boston, 2001), doi: 10.1007/978-1-4612-0123-6. Zbl0979.05001

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.