A Problem on Edge-magic Labelings of Cycles

López, S. C. ; Muntaner-Batle, F. A. ; Rius-Font, M.

Canadian mathematical bulletin, Tome 57 (2014) no. 2, pp. 375-380

Résumé

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

Détail

DOI : 10.4153/CMB-2013-036-1

Mots-clés : 05C78, edge-magic, valence, ⊕h

Bibliographie

[1] [1] Acharya, B. D. and Hegde, S. M., Strongly indexable graph. Discrete Math. 93 (1991, no. 2–3, 123–129. Google Scholar | DOI

[2] [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] [3] Bača, M. and Miller, M., Super edge-antimagic graphs. BrownWalker Press, Boca Raton, 2008. Google Scholar

[4] [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. 361–373. Google Scholar

[5] [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] [6] Enomoto, H., Lladö, A., Nakamigawa, T., and Ringel, G., Super edge-magic graphs. SUT J. Math. 34 (1998, no. 2, 105–109. Google Scholar

[7] [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, 189–216. Google Scholar

[8] [8] Gallian, J. A., A dynamic survey of graph labeling. Electron. J. Combin. 5 (1998, DS6. Google Scholar

[9] [9] Godbold, R. D. and Slater, P. J., All cycles are edge-magic. Bull. Inst. Combin. Appl. 22 (1998, 93–97. Google Scholar

[10] [10] Kotzig, A. and Rosa, A., Magic valuations of finite graphs. Canad. Math. Bull. 13 (1970, 451–461. Google Scholar | DOI

[11] [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, 137–152. Google Scholar | DOI

[12] [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, 199–208. Google Scholar

[13] [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] [14] McQuillan, D., Edge-magic and vertex-magic total labelings of certain cycles. Ars Combin. 91 (2009, 257–266. Google Scholar

[15] [15] Wallis, W. D., Magic graphs. Birkhaüser Boston Inc., Boston, MA 2001. Google Scholar