Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-19T22:44:53.871Z Has data issue: false hasContentIssue false

A Problem on Edge-magic Labelings of Cycles

Published online by Cambridge University Press:  20 November 2018

S. C. López
Affiliation:
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, BarcelonaTech, C/Esteve Terrades 5, 08860 Castelldefels, Spain e-mail: [email protected]@gmail.com
F. A. Muntaner-Batle
Affiliation:
Graph Theory and Applications Research Group, School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, The University of Newcastle, NSW 2308 Australia e-mail: [email protected]
M. Rius-Font
Affiliation:
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, BarcelonaTech, C/Esteve Terrades 5, 08860 Castelldefels, Spain e-mail: [email protected]@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In 1970, Kotzig and Rosa defined the concept of edge-magic labelings as follows. Let $G$ be a simple $\left( p,\,q \right)$-graph (that is, a graph of order $p$ and size $q$ without loops or multiple edges). A bijective function $f:\,V\left( G \right)\cup E\left( G \right)\,\to \,\left\{ 1,\,2,\,.\,.\,.\,,\,p\,+\,q \right\}$ is an edge-magic labeling of $G$ if $f\left( u \right)\,+\,f\left( uv \right)\,+f\left( v \right)\,=\,k$, for all $uv\,\in \,E\left( G \right)$. A graph that admits an edge-magic labeling is called an edge-magic graph, and $k$ is called the magic sum of the labeling. An old conjecture of Godbold and Slater states that all possible theoretical magic sums are attained for each cycle of order $n\,\ge \,7$. Motivated by this conjecture, we prove that for all ${{n}_{0}}\,\in \,\mathbb{N}$, there exists $n\,\in \,\mathbb{N}$ such that the cycle ${{C}_{n}}$ admits at least ${{n}_{0}}$ edge-magic labelings with at least ${{n}_{0}}$ mutually distinct magic sums. We do this by providing a lower bound for the number of magic sums of the cycle ${{C}_{n}}$, depending on the sum of the exponents of the odd primes appearing in the prime factorization of $n$.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 2014

Footnotes

The first and the third author are supported by the Spanish Research Council under project MTM2011-28800-C02-01 and by the Catalan Research Council under grant 2009SGR1387.

References

[1] Acharya, B. D. and Hegde, S. M., Strongly indexable graph. Discrete Math. 93 (1991, no. 23, 123129.http://dx.doi.org/10.1016/0012-365X(91)90248-Z CrossRefGoogle Scholar
[2] Ahmad, A., Muntaner-Batle, F. A., and Rius-Font, M., On the product and other related topics. Ars Combin., to appear.Google Scholar
[3] Bača, M. and Miller, M., Super edge-antimagic graphs. BrownWalker Press, Boca Raton, 2008.Google Scholar
[4] Baker, A. and Sawada, J., Magic labelings on cycles and wheels. In: Combinatorial optimization and applications, Lecture Notes in Comput. Sci., 5165, Springer, Berlin, 2008, pp. 361373.Google Scholar
[5] Chartrand, G. and Lesniak, L., Graphs and digraphs. Second ed., TheWadsworth & Brooks/Cole Mathematics Series,Wadsworth & Brooks/Cole Advanced Books and Software, Monterey, CA, 1986.Google Scholar
[6] Enomoto, H., Lladö, A., Nakamigawa, T., and Ringel, G., Super edge-magic graphs. SUT J. Math. 34 (1998, no. 2, 105109.Google Scholar
[7] Figueroa-Centeno, R. M., R. Ichishima, Muntaner-Batle, F. A., and M. Rius-Font, Labeling generating matrices. J. Combin. Math. Combin. Comput. 67 (2008, 189216.Google Scholar
[8] Gallian, J. A., A dynamic survey of graph labeling. Electron. J. Combin. 5 (1998, DS6.Google Scholar
[9] Godbold, R. D. and Slater, P. J., All cycles are edge-magic. Bull. Inst. Combin. Appl. 22 (1998, 9397.Google Scholar
[10] Kotzig, A. and Rosa, A., Magic valuations of finite graphs. Canad. Math. Bull. 13 (1970, 451461.http://dx.doi.org/10.4153/CMB-1970-084-1 CrossRefGoogle Scholar
[11] Löpez, S. C., Muntaner-Batle, F. A., and Rius-Font, M., Bi-magic and other generalizations of super edge-magic labelings. Bull. Aust. Math. Soc. 84 (2011, no. 1, 137152.CrossRefGoogle Scholar
[12] Löpez, S. C., Muntaner-Batle, F. A., and Rius-Font, M., Perfect super edge-magic graphs. Bull. Math. Soc. Sci. Math. Roumanie 55(103) (2012), no. 2, 199208.Google Scholar
[13] Löpez, S. C., Muntaner-Batle, F. A., and Rius-Font, M., Perfect edge-magic graphs. Bull. Math. Soc. Sci. Math. Roumanie, to appear.Google Scholar
[14] McQuillan, D., Edge-magic and vertex-magic total labelings of certain cycles. Ars Combin. 91 (2009, 257266.Google Scholar
[15] Wallis, W. D., Magic graphs. Birkhaüser Boston Inc., Boston, MA 2001.Google Scholar