On kk-minimum and mm-minimum edge-magic injections of graphs

An edge-magic total labelling (EMTL) of a graph GG with nn vertices and ee edges is an injection λ:V(G)∪E(G)→[n+e]λ:V(G)∪E(G)→[n+e], where, for every edge uv∈E(G)uv∈E(G), we have wtλ(uv)=kλwtλ(uv)=kλ, the magic sum of λλ. An edge-magic injection (EMI) μμ of GG is an injection μ:V(G)∪E(G)→Nμ:V(G)∪E(G)→N with magic sum kμkμ and largest label mμmμ. For a graph GG we define and study the two parameters κ(G)κ(G): the smallest kμkμ amongst all EMI’s μμ of GG, and m(G)m(G): the smallest mμmμ amongst all EMI’s μμ of GG. We find κ(G)κ(G) for G∈GG∈G for many classes of graphs GG. We present algorithms which compute the parameters κ(G)κ(G) and m(G)m(G). These algorithms use a GG-sequence: a sequence of integers on the vertices of GG whose sum on edges is distinct. We find these parameters for all GG with up to 7 vertices. We introduce the concept of a double-witness: an EMI μμ of GG for which both kμ=κ(G)kμ=κ(G) and mμ=m(G)mμ=m(G); and present an algorithm to find all double-witnesses for GG. The deficiency of GG, def(G)def(G), is m(G)−n−em(G)−n−e. Two new graphs on 6 vertices with def(G)=1def(G)=1 are presented. A previously studied parameter of GG is κEMTL(G)κEMTL(G), the magic strength of GG: the smallest kλkλ amongst all EMTL’s λλ of GG. We relate κ(G)κ(G) to κEMTL(G)κEMTL(G) for various GG, and find a class of graphs BB for which κEMTL(G)−κ(G)κEMTL(G)−κ(G) is a constant multiple of n−4n−4 for G∈BG∈B. We specialise to G=KnG=Kn, and find both κ(Kn)κ(Kn) and m(Kn)m(Kn) for all n≤11n≤11. We relate κ(Kn)κ(Kn) and m(Kn)m(Kn) to known functions of nn, and give lower bounds for κ(Kn)κ(Kn) and m(Kn)m(Kn).