Skip to main content
On k-minimum and m-minimum Edge-Magic Injections of Graphs
Articles and Preprints
  • John P. McSorley, Southern Illinois University Carbondale
  • John A. Trono, Saint Michaels College
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
Publication Date

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 uvE(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 and largest label . For a graph G we define and study the two parameters κ(G): the smallest amongst all EMI’s μ of G, and m(G): the smallest amongst all EMI’s μ of G. We find κ(G) for GG 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 =κ(G) and =m(G) ; and present an algorithm to find all double-witnesses for G. The deficiency of G, def(G), is m(G)−ne. 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 GB. 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).

Citation Information
John P. McSorley and John A. Trono. "On k-minimum and m-minimum Edge-Magic Injections of Graphs" (2010)
Available at: