Download PDF - A magical approach to some labeling conjecturesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A magical approach to some labeling conjectures

Authors 1, 2, 3, 4

Affiliations

  1. Mathematics Department, University of Hawai'i at Hilo, 200 W. Kawili St., Hilo, HI 96720, USA
  2. College of Humanities and Sciences, Nihon University, 3-25-40 Sakurajosui Setagaya-ku, Tokyo 156-8550, Japan
  3. Graph Theory and Applications Research Group, School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, University of Newcastle, NSW 2308, Australia
  4. Department of Mathematical Information Science, Faculty of Science, Tokyo University of Science, 1-3, Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan

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.

Keywords

ENG
edge-magic labelling, edge-magic total labelling, felicitous labelling, harmonious labelling, sequential labelling

Bibliography

  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.
  2. G. Chartrand and L. Lesniak, Graphs and Digraphs (Wadsworth & Brook/Cole Advanced Books and Software, Monterey, Calif. 1986).
  3. H. Enomoto, A. Lladó, T. Nakamigawa and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998) 105-109.
  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.
  5. R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On super edge-magic graphs, Ars Combin. 64 (2002) 81-96.
  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.
  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.
  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.
  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. R. Frucht and L.C. Salinas, Graceful numbering of snakes with constraints on the first label, Ars Combin. (B) 20 (1985) 143-157.
  11. J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (2009) #DS6.
  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.
  13. T. Grace, On sequential labelings of graphs, J. Graph Theory 7 (1983) 195-201, doi: 10.1002/jgt.3190070208.
  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.
  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.
  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.
  17. A. Kotzig, β-valuations of quadratic graphs with isomorphic components, Utilitas Math. 7 (1975) 263-279.
  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.
  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.
  20. M. Seoud, A.E.I. Abdel Maqsoud and J. Sheehan, Harmonious graphs, Utilitas Math. 47 (1995) 225-233.
  21. S.C. Shee, On harmonious and related graphs, Ars Combin. 23 (1987) 237-247.
  22. S.C. Shee and S.M. Lee, On harmonious and felicitous labelings of graphs, Congress Numer. 68 (1989) 155-170.
  23. G. Ringel and A. Lladó, Another tree conjecture, Bull. Inst. Combin. Appl. 18 (1996) 83-85.
  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. W.D. Wallis, Magic Graphs (Birkhäuser, Boston, 2001), doi: 10.1007/978-1-4612-0123-6.
Discussiones Mathematicae Graph Theory
2011/31/1
Export to PBN, Opens in new tab
Pages:
79-113
Main language of publication
English
Received
2009-09-21
Accepted
2010-04-06
Published
2011

DOI: 10.7151/dmgt.1531

Exact and natural sciences