## 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

**for which κ**

*B*_{EMTL}(

*G*)−κ(

*G*) is a constant multiple of

*n*−4 for

*G*∈

*. We specialise to*

**B***G*=

*K*, and find both κ(

_{n}*K*) and

_{n}**m**(

*K*) for all

_{n}*n*≤11. We relate κ(

*K*) and

_{n}**m**(

*K*) to known functions of

_{n}*n*, and give lower bounds for κ(

*K*) and

_{n}**m**(

*K*).

_{n}## 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 andm-minimum edge-magic injections of graphs. Discrete Mathematics, 310(1), 56-69. doi: 10.1016/j.disc.2009.07.021