Abstract view
A Problem on Edgemagic Labelings of Cycles


Published:20131012
Printed: Jun 2014
S. C. López,
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. BarcelonaTech, C/Esteve Terrades 5, 08860 Castelldefels, Spain
MuntanerBatle,
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
RiusFont,
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. BarcelonaTech, C/Esteve Terrades 5, 08860 Castelldefels, Spain
Abstract
Kotzig and Rosa defined in 1970 the concept of edgemagic labelings as
follows: let $G$ be a simple $(p,q)$graph (that is, a graph of order $p$
and size $q$ without loops or multiple edges). A bijective function $f:V(G)\cup
E(G)\rightarrow \{1,2,\ldots,p+q\}$ is an edgemagic labeling of $G$ if
$f(u)+f(uv)+f(v)=k$, for all $uv\in E(G)$. A graph that admits an edgemagic
labeling is called an edgemagic graph, and $k$ is called the magic sum
of the labeling. An old conjecture of Godbold and Slater sets 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$ edgemagic 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$.