*k*-minimum and

*m*-minimum Edge-Magic Injections of Graphs

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*∈

*. We specialise to*

**B***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*).

Available at: http://works.bepress.com/john_trono/2/

k-minimum andm-minimum edge-magic injections of graphs. Discrete Mathematics, 310(1), 56-69. doi: 10.1016/j.disc.2009.07.021