Abstract
An edge-magic total labelling (EMTL) of a graph G with n vertices and e edges is an injection λ:V(G) ∪ E(G)→[n+e], where, for every edge uv ∈ E(G), we have wtλ(uv)=kλ, the magic sum of λ. An edge-magic injection (EMI) μ of G is an injection μ : V(G) ∪ E(G) → N with magic sum kμ and largest label mμ. For a graph G we define and study the two parameters κ(G): the smallest kμ amongst all EMI’s μ of G, and m(G): the smallest mμ amongst all EMI’s μ of G. We find κ(G) for G ∈ G for many classes of graphs G. We present algorithms which compute the parameters κ(G) and m(G). These algorithms use a G-sequence: a sequence of integers on the vertices of G whose sum on edges is distinct. We find these parameters for all G with up to 7 vertices. We introduce the concept of a double-witness: an EMI μ of G for which both kμ=κ(G) and mμ=m(G) ; and present an algorithm to find all double-witnesses for G. The deficiency of G, def(G), is m(G)−n−e. Two new graphs on 6 vertices with def(G)=1 are presented. A previously studied parameter of G is κEMTL(G), the magic strength of G: the smallest kλ amongst all EMTL’s λ of G. We relate κ(G) to κEMTL(G) for various G, and find a class of graphs B for which κEMTL(G)−κ(G) is a constant multiple of n−4 for G ∈B. We specialise to G=Kn, and find both κ(Kn) and m(Kn) for all n≤11. We relate κ(Kn) and m(Kn) to known functions of n, and give lower bounds for κ(Kn) and m(Kn).
Recommended Citation
McSorley, John P. and Trono, John A. "On k-minimum and m-minimum Edge-Magic Injections of Graphs." (Jan 2010).
Comments
Published in McSorley, J. P., & Trono, J. A. (2010). On k-minimum and m-minimum edge-magic injections of graphs. Discrete Mathematics, 310(1), 56-69. doi: 10.1016/j.disc.2009.07.021