ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 31(1) (2011) 79-113
DOI: 10.7151/dmgt.1531


Ramon M. Figueroa-Centeno

Mathematics Department, University of Hawai'i at Hilo
200 W. Kawili St., Hilo, HI 96720, USA

Rikio Ichishima

College of Humanities and Sciences, Nihon University
3-25-40 Sakurajosui Setagaya-ku, Tokyo 156-8550, Japan

Francesc A. Muntaner-Batle

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

Akito Oshima

Department of Mathematical Information Science
Faculty of Science, Tokyo University of Science
1-3, Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan


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: edge-magic labelling, edge-magic total labelling, felicitous labelling, harmonious labelling, sequential labelling.

2010 Mathematics Subject Classification: 05C78.


[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.

Received 21 September 2009
Revised 6 April 2010
Accepted 6 April 2010