On k-minimum and m-minimum Edge-Magic Injections of Graphs

John P. McSorley^{∗} Department of Mathematics Mailcode 4408 Southern Illinois University Carbondale, IL 62901-4408 mcsorley60@hotmail.com

John A. Trono Department of Computer Science Saint Michael’s College Box 243 One Winooski Park Colchester, VT 05439 jtrono@smcvt.edu

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 edgemagic injection (EMI) μ of G is an injection μ: V (G) ∪ E(G) → ℕ 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 𝔪(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 𝔪(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_{μ} = 𝔪(G); and present an algorithm to find all double-witnesses for G. The deficiency of G, def(G), is 𝔪(G)−n−e. Two new graphs on 6 vertices with def(G) = 1 are presented. A previously studied parameter of G is κ_{EMT L}(G), the magic strength of G: the smallest k_{λ} amongst all EMTL’s λ of G. We relate κ(G) to κ_{EMT L}(G) for various G, and find a class of graphs B for which κ_{EMT L}(G) − κ(G) is a constant multiple of n − 4 for G ∈ B. We specialize to G = K_{n}, and find both κ(K_{n}) and 𝔪(K_{n}) for all n ≤ 11. We relate κ(K_{n}) and 𝔪(K_{n}) to known functions of n, and give lower bounds for κ(K_{n}) and 𝔪(K_{n}).

Keywords: edge-magic injection; magic strength; G-sequence; k-minimum G-sequence; m-minimum G-sequence; Well Spread-sequence; double-witness.

1 Introduction, κ(G), 𝔪(G)

We use ℕ = {1, 2, 3, …} for the set of natural numbers, and [s] = {1, 2, …, s} for the set of the first s natural numbers. Here G will be a simple graph without isolated vertices, with vertex-set V (G) of order n ≥ 2, and edge-set E(G) of size e ≥ 1. Consider an injection μ : V (G) ∪ E(G) → ℕ, which we represent by labelling each vertex and edge of G with a distinct natural number, this is a total labelling of G. For edge uv ∈ E(G) let its weight under μ be wt_{μ}(uv) = μ(u) + μ(v) + μ(uv).

A magic valuation of G is an injection λ : V (G) ∪ E(G) → [n + e], where, for every edge uv ∈ E(G), we have wt_{λ}(uv) = k_{λ}, for a constant k_{λ}, called the magic sum of λ. Magic valuations were introduced by Kotzig and Rosa in [5], and have been studied further under the name edge-magic total labellings (EMTL’s). Here we use ‘EMTL’ instead of ‘magic valuation’. Wallis, Baskoro, Miller, and Slamin [14], and Wallis [13] contain much information about EMTL’s. See Gallian [2] for numerous classes of graphs that have an EMTL, and for other information on this and related topics. There is now extensive ongoing research in the field of graph labellings, much of it stimulated by magic valuations which were amongst the first labellings studied.

Here we focus on edge-magic injections of a graph G. Definitions: Edge-magic injection (EMI) of G; k_{μ}, m_{μ}

(1) The injection μ is an edge-magic injection of G if for every edge uv ∈ E(G) we have wt_{μ}(uv) = k_{μ}, for some constant k_{μ} called the magic sum of μ.

(2) m_{μ} is the largest label used in μ. So μ: V (G) ∪ E(G) → [m_{μ}].

Thus an EMI of G is a relaxed form of an EMTL of G, in that the labels of G can be any natural number. The idea of an EMI also comes from [5]. Not every graph has an EMTL, an example is K_{4}. But every graph has an EMI (see Theorem 3.1) and this is one advantage of studying EMI’s over studying EMTL’s. It appears that very little research has been carried out on EMI’s as compared to EMTL’s.

One avenue of research in EMTL’s is to extend the list of graphs that have an EMTL. Another is to investigate properties of EMTL’s. With this second idea in mind Avadayappan, Vasuki, and Jeyanthi [1] defined the following parameter, called the magic strength of G, for any graph G that has an EMTL. We denote this parameter by κ_{EMT L}(G). Definition: κ_{EMT L}(G)

Let G have an EMTL. Then

κ_{EMT L}(G) = min{k_{λ} | λ is an EMTL of G with magic sum k_{λ}},

is the smallest k_{λ} amongst all EMTL’s λ of G.

All known values of κ_{EMT L}(G) are given in Theorem 1.1 below.

In [6] it was shown that K_{n} has an EMTL if and only if n ∈ {2, 3, 5, 6}. The values of κ_{EMT L}(K_{n}) for n ∈ {2, 3, 5, 6} in line 1 of Theorem 1.1 come from Section 7.1 of [14] where all such EMTL’s were found, although κ_{EMT L}(G) was not considered; see also Section 2.3.3 of [13]. The values of κ_{EMT L}(G) for the graphs G in lines 2–6 of Theorem 1.1 are from [1], and those in lines 7 and 8 are from Section 2 of Murugan [7]. Remark: All graphs G in Theorem 1.1 that contain an ‘n’ in their notation have n vertices, except for G = B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗} which has n + 1 vertices.

K_{n}, P_{n}, and C_{n} represent the complete graph, the path, and the cycle respectively. The bi-star B_{\frac{n−2}{2} , \frac{n−2}{2}} for n even and ≥ 4 is obtained from two disjoint copies of the star K_{1, \frac{n−2}{2}} by joining the center vertices with a new edge; and B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗} is obtained from B_{\frac{n−2}{2} , \frac{n−2}{2}} by subdividing this new edge with a new vertex, it has n + 1 vertices. The Huffman tree HT_{\frac{n+1}{2}} for n odd and ≥ 3 is the path P_{\frac{n+1}{2}} with a pendant edge attached to every vertex except the last. The twig T W\frac{n}{3} for n ≡ 3 (mod 6) is the path P\frac{n}{3} with two pendant edges attached to every vertex.

Theorem 1.1 ([14], [1], [7])

κ_{EMT L}(G) = \begin{cases}6, 9, 18, 25, & G = K_{2}, K_{3}, K_{5}, K_{6}; \\ ⌈\frac{5n + 3}{2}⌉, & G = C_{n}, (n ≥ 3); \\ \frac{9n + 6}{4}, & G = \frac{n}{2}K_{2}, (n ≡ 2 (mod 4)); \\ ⌈\frac{5n + 1}{2}⌉, & G = P_{n}, (n ≥ 2); \\ \frac{5n + 2}{2}, & G = B_{\frac{n−2}{2} , \frac{n−2}{2}} , (n even and ≥ 4); \\ 2n + 5, & G = B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗} , (n even and ≥ 4); \\ ⌈\frac{9n + 5}{4}⌉, & G = HT_{\frac{n+1}{2}} , (n odd and ≥ 3); \\ \frac{13n + 9}{6}, & G = T W\frac{n}{3} , (n ≡ 3 (mod 6)). \end{cases}

Because every graph G has an EMI, we may define a new parameter, κ(G) = κ_{EMI}(G), as a more general version of κ_{EMT L}(G). It appears that κ(G) has not been considered before. Definitions: κ(G), k-minimum EMI of G; witness for κ(G)

(1) κ(G) = min{k_{μ} | μ is an EMI of G with magic sum k_{μ}}, is the smallest k_{μ} amongst all EMI’s μ of G.

(2) EMI μ is a k-minimum EMI of G if k_{μ} = κ(G); and μ is a witness for κ(G).

See Sections 3 and 4 of [7] for related, but different, parameters of G; and see Kong, Lee, and Sun [3] for a similar parameter, but concerning the vertices of G.

The second parameter of a graph G which we consider is 𝔪(G). Definitions: 𝔪(G), m-minimum EMI of G; witness for 𝔪(G), def(G)

(1) 𝔪(G) = min{m_{μ} | μ is an EMI of G with largest label m_{μ}}, is the smallest m_{μ} amongst all EMI’s μ of G.

(2) EMI μ is a m-minimum EMI of G if m_{μ} = 𝔪(G); and μ is a witness for 𝔪(G).

(3) def(G) = 𝔪(G) − n − e, the deficiency of G, is the smallest number such that there exists an EMI μ: V (G) ∪ E(G) → [n + e + def(G)].

The concept of ‘deficiency’ comes from [5]; the formulation we use is slightly different from that used there. By Definition (1) above it is clear that 𝔪(G) = n + e if and only if G has an EMTL (if and only if def(G) = 0). As an example of some graphs G with 𝔪(G) = n + e + 1 (equivalently, def(G) = 1) see the 10 graphs shown in [5], each has n ≤ 6.

We summarize our paper:

In Section 2 we give a lower bound for κ(G), and then find κ(G) for all incomplete graphs G in Theorem 1.1. In Section 3 we define a G-sequence A, and show that every graph G on n vertices has an EMI. In Section 4 we present algorithms that, for a fixed G, compute κ(G), and find all witnesses for κ(G), i.e., all k-minimum EMI’s of G. In Section 5 we present algorithms that compute 𝔪(G), and find all witnesses for 𝔪(G), i.e., find all m-minimum EMI’s of G. In Section 6 we present our results from the algorithms of Sections 4 and 5 for graphs G with n = 2, 3, 4, 5, or 6 vertices. We find two new graphs G with def(G) = 1 on 6 vertices. We also consider graphs G with n = 7 vertices, and trees T with up to n = 10 vertices. In Section 7 we specialize to G = K_{n}. Finally, in Section 8, we consider miscellaneous items.

2 κ(G) for certain G

In this section we find κ(G) for all graphs G in Theorem 1.1 except for G = K_{n} where n ∈ {2, 3, 5, 6}. In Section 7 we show κ(K_{n}) = κ_{EMT L}(K_{n}) for all n ∈ {2, 3, 5, 6}, (see Table 3).

If a graph G has an EMTL then, since an EMTL of G is an EMI of G, we have

κ(G) ≤ κ_{EMT L}(G).  (1)

However κ(G) < κ_{EMT L}(G) is possible. From [1] the graph B_{2,2} has κ_{EMT L}(B_{2,2}) = 16, but see Fig. 1 for an EMI μ of B_{2,2} with k_{μ} = 15 < 16. Indeed, in Theorem 2.4(ii), we show that κ(B_{2,2}) = 15.

In Theorem 2.1 below we let V (G) = {v_{1}, v_{2}, …, v_{n}} and let d_{i} denote the degree of vertex v_{i} for i = 1, 2, …, n. We order the vertices so that d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n}.

•  • • •  • • 12  4  3  78_{6}_{11}_{10} _{9}  _{5} k_{λ} = 16, m_{λ} = 11 EMTL
• •

•

•

•

•

3

4 1 2 6

5

11 7

10 12

8

k_{μ} = 15, m_{μ} = 12 EMI, label 9 unused

Figure 1: A k-minimum EMTL and a k-minimum EMI of B_{2,2}

Theorem 2.1 Let G have n vertices, e edges, and vertex degrees [d_{1}, d_{2}, …, d_{n}] where d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{n}. Then

(i) κ(G) ≥ ⌈\frac{6ne + e^{2} + 3e + 2𝔪(G) − 2n − 2 ∑_{i=1}^{n} i d_{i}}{2e} ⌉,

(ii) κ(G) ≥ ⌈\frac{6ne + e^{2} + 5e − 2 ∑_{i=1}^{n} i d_{i}}{2e} ⌉.

Proof. (i) Let μ be an EMI of G with magic sum κ(G) and with largest label m_{μ}. When summing κ(G) over every edge, each edge label μ(uv) appears one time and each vertex label μ(v_{i}) appears d_{i} times. That is,

eκ(G) = ∑_{uv∈E(G)} μ(uv) + ∑_{v_{i}∈V (G)} d_{i} μ(v_{i}).  (2)

In order to minimize the RHS of Equation (2) we use the n + e labels {1, 2, …, n + e − 1, m_{μ}} on G. We place the largest e labels {n + 1, n + 2, …, n + e − 1, m_{μ}} on the e edges; and the smallest n labels {1, 2, …, n} on the n vertices in reverse order, so that μ(v_{i}) = n − i + 1 for i = 1, 2, …, n. So

eκ(G) ≥ \frac{2ne + 2m_{μ} + e^{2} − 2n − e}{2} + ∑_{i=1}^{n} d_{i} (n − i + 1).

Now, using ∑_{i=1}^{n} d_{i} = 2e, and m_{μ} ≥ 𝔪(G), and noting that κ(G) is an integer, gives the result.

(ii) Use (i) and 𝔪(G) ≥ n + e.

Corollary 2.2 Let G be a r-regular graph with n vertices and e edges. Then

(i) κ(G) ≥ ⌈\frac{4ne + e^{2} + e + 2𝔪(G) − 2n}{2e}⌉,

(ii) κ(G) ≥ ⌈\frac{4n + e + 3}{2}⌉.

Proof. For (i) we use Theorem 2.1, and nr = 2e, and ∑_{i=1}^{n} i = \binom{n+1}{2}. And for (ii) we use (i) and 𝔪(G) ≥ n + e.

The graphs G in lines 2 and 3 in Theorem 1.1 are regular, we have:

Theorem 2.3

(i) κ(C_{n}) = κ_{EMT L}(C_{n}) = ⌈\frac{5n + 3}{2}⌉, (n ≥ 3).

(ii) κ(\frac{n}{2}K_{2}) = κ_{EMT L}(\frac{n}{2}K_{2}) = \frac{9n + 6}{4}, (n ≡ 2 (mod 4)).

Proof. (i) When G = C_{n} we have e = n, and Corollary 2.2(ii) gives κ(C_{n}) ≥ ⌈\frac{5n+3}{2}⌉ = κ_{EMT L}(C_{n}). The upperbound κ(C_{n}) ≤ κ_{EMT L}(C_{n}) comes from Equation (1). The proof of (ii) is similar using e = \frac{n}{2}.

Now for the irregular G in lines 4–8 in Theorem 1.1 we have:

Theorem 2.4

(i) κ(P_{n}) = κ_{EMT L}(P_{n}) = ⌈\frac{5n + 1}{2}⌉, (n ≥ 2).

(ii) κ(B_{\frac{n−2}{2} , \frac{n−2}{2}} ) = 2n + 3, (n even and ≥ 4). (iii) κ(B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗}) = κ_{EMT L}(B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗}) = 2n + 5, (n even and ≥ 4).

(iv) κ(HT_{\frac{n+1}{2}} ) = κ_{EMT L}(HT_{\frac{n+1}{2}} ) = ⌈\frac{9n + 5}{4}⌉, (n odd and ≥ 3).

(v) κ(T W\frac{n}{3} ) = κ_{EMT L}(T W\frac{n}{3} ) = \frac{13n + 9}{6}, (n ≡ 3 (mod 6)).

Proof. (i) Here G = P_{n} with n vertices and e = n − 1 edges and degrees [1, 1, \overbrace{2, …, 2}^{n−2}], so ∑ id_{i} = n^{2} + n − 3. Then Theorem 2.1(ii) gives κ(P_{n}) ≥ ⌈\frac{5n}{2} + \frac{1}{n−1}⌉ = ⌈\frac{5n+1}{2}⌉. And κ(P_{n}) ≤ κ_{EMT L}(P_{n}) = ⌈\frac{5n+1}{2}⌉ comes from Theorem 1.1 and Equation (1). Thus κ(P_{n}) = κ_{EMT L}(P_{n}) = ⌈\frac{5n+1}{2}⌉. (ii) Here G = B_{\frac{n−2}{2} , \frac{n−2}{2}} with n vertices and e = n − 1 edges and degrees

[\overbrace{1, …, 1}^{n−2}, \frac{n}{2}, \frac{n}{2}], so ∑ id_{i} = \frac{3n^{2}−4n+2}{2}. Then Theorem 2.1(ii) gives κ(B_{\frac{n−2}{2} , \frac{n−2}{2}} ) ≥

⌈\frac{4n+5}{2} − \frac{1}{2(n−2)}⌉ = 2n + 3. Now consider the EMI μ of B_{\frac{n−2}{2} , \frac{n−2}{2}} shown below. It has k_{μ} = 2n + 3 and m_{μ} = 2n, label \frac{3n}{2} is unused. Hence κ(B_{\frac{n−2}{2} , \frac{n−2}{2}} ) ≤ 2n + 3, and so κ(B_{\frac{n−2}{2} , \frac{n−2}{2}} ) = 2n + 3.

•
•
•
•

n + 1

2

n

n + 2 n − 1 ⋮

\frac{3n−4}{2}

\frac{n+6}{2}

\frac{3n−2}{2}

\frac{n+4}{2}

• • 2n

•
•
•
•

1

2n − 1

3

2n − 2 4 ⋮

\frac{n}{2} \frac{3n+4}{2}

\frac{n+2}{2}

\frac{3n+2}{2}

(iii) Here G = B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗} with n + 1 vertices and e = n edges and degrees

[\overbrace{1, …, 1}^{n−2}, 2, \frac{n}{2}, \frac{n}{2}], so ∑ id_{i} = \frac{3n^{2}+2n−2}{2}. Theorem 2.1(ii) gives κ(B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗}) ≥

⌈\frac{4n+9}{2} + \frac{1}{n}⌉ = 2n + 5. And we have κ(B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗}) ≤ 2n + 5 from Theorem 1.1 and Equation (1). Thus κ(B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗}) = κ_{EMT L}(B_{\frac{n−2}{2} , \frac{n−2}{2}}^{∗}) = 2n + 5. (iv) Here G = HT_{\frac{n+1}{2}} with n vertices and e = n − 1 edges and degrees

[\overbrace{1, …, 1}^{\frac{n+1}{2}}, 2, \overbrace{3, …, 3}^{\frac{n−3}{2}}], so ∑ id_{i} = \frac{5n^{2}−9}{4}. Again Theorem 2.1(ii) gives κ(HT_{\frac{n+1}{2}} ) ≥

⌈\frac{9n+3}{4} + \frac{1}{2n−2}⌉ = ⌈\frac{9n+5}{4}⌉, and κ(HT_{\frac{n+1}{2}} ) ≤ ⌈\frac{9n+5}{4}⌉ from Theorem 1.1 and Equation (1). Thus κ(HT_{\frac{n+1}{2}} ) = κ_{EMT L}(HT_{\frac{n+1}{2}} ) = ⌈\frac{9n+5}{4}⌉.

(v) Here G = T W\frac{n}{3} with n vertices and e = n − 1 edges and degrees

[\overbrace{1, …, 1}^{\frac{2n}{3}}, 3, 3, \overbrace{4, …, 4}^{\frac{n−6}{3}}], so ∑ id_{i} = \frac{4n^{2}−n−9}{3}. Theorem 2.1(ii) gives κ(T W\frac{n}{3} ) ≥

⌈\frac{13n+6}{6} + \frac{2}{n−1}⌉ = \frac{13n+9}{6}, and κ(T W\frac{n}{3} ) ≤ \frac{13n+9}{6} from Theorem 1.1 and Equation (1). Thus κ(T W\frac{n}{3} ) = κ_{EMT L}(T W\frac{n}{3} ) = \frac{13n+9}{6}.

Remark: See Figure 1 for an example of the EMI of Theorem 2.4(ii) with n = 6. We have κ_{EMT L}(B_{\frac{n−2}{2} , \frac{n−2}{2}} ) − κ(B_{\frac{n−2}{2} , \frac{n−2}{2}} ) = \frac{n−4}{2}. Hence, for a graph G with n vertices, we can have the difference κ_{EMT L}(G) − κ(G) as large as a constant multiple of n − 4, i.e., a constant multiple of n for sufficiently large n.

We conclude this section with the following result which could be useful when searching for an EMI μ of G with k_{μ} < κ_{EMT L}(G) for regular G with an EMTL.

Theorem 2.5 Let G be a r-regular graph (r ≥ 2) with an EMTL, and let λ be a witness for κ_{EMT L}(G), so k_{λ} = κ_{EMT L}(G). Now suppose that μ is an EMI of G with k_{μ} < κ_{EMT L}(G). Then

∑_{u∈V (G)} μ(u) < ∑_{u∈V (G)} λ(u).

Proof. Let S_{λ} = ∑_{u∈V (G)} λ(u) + ∑_{uv∈E(G)} λ(uv) be the sum of all the labels of λ, define S_{μ} similarly.

Now λ is an EMTL of G with k_{λ} = κ_{EMT L}(G), so

eκ_{EMT L}(G) = ∑_{u∈V (G)} rλ(u) + ∑_{uv∈E(G)} λ(uv) = (r − 1) ∑_{u∈V (G)} λ(u) + S_{λ}.

The first equality is true since each vertex label λ(u) appears r times and each edge label λ(uv) appears one time when summing κ_{EMT L}(G) over every edge. Similarly,

ek_{μ} = (r − 1) ∑_{u∈V (G)} μ(u) + S_{μ}.

Now k_{μ} < κ_{EMT L}(G) so μ is not an EMTL of G, and thus S_{λ} < S_{μ}. So

eκ_{EMT L}(G) − (r − 1) ∑_{u∈V (G)} λ(u) < ek_{μ} − (r − 1) ∑_{u∈V (G)} μ(u).

So

(r − 1) ( ∑_{u∈V (G)} μ(u) − ∑_{u∈V (G)} λ(u)) < e (k_{μ} − κ_{EMT L}(G)) < 0.

The last inequality is true since k_{μ} < κ_{EMT L}(G). But r ≥ 2, and so

∑_{u∈V (G)} μ(u) < ∑_{u∈V (G)} λ(u).

3 G-sequences

Let S and T be sets of distinct natural numbers, ordered or unordered. Definitions: S↑, S↓, S + T

(1) S↑= max{s | s ∈ S}, is the largest element in S.

(2) S↓= min{s | s ∈ S}, is the smallest element in S.

(3) S + T = {s + t | s ∈ S, t ∈ T }.

Let G have vertex set V (G) = (v_{1}, v_{2}, …, v_{n}) for n ≥ 2, fixed in this order. Let A = (a_{1}, a_{2}, …, a_{n}) be an ordered sequence of n distinct natural numbers. Now label vertex v_{i} with a_{i}, say ℓ(v_{i}) = a_{i}, for each i = 1, 2, …, n. Definitions: P(A), G-sequence, G(A)′, k(G(A)), E(A), G(A), m(G(A))

(1) P(A) = {a_{i} + a_{j} | v_{i}v_{j} ∈ E(G), 1 ≤ i < j ≤ n}.

(2) A is a G-sequence if each a_{i} + a_{j} ∈ P(A) is distinct, equivalently, if |P(A)| = e = |E(G)|.

(3) G(A)′ is the graph G whose vertices have been labelled with elements of A.

(4) k(G(A)) is the smallest integer ≥ P(A)↑ + 1 that lies outside A+P(A). That is, k(G(A)) = min\{[P(A)↑ + 1, ∞) ∩ \overline{(A + P(A))}\}.

(5) E(A) = {k(G(A)) − a_{i} − a_{j} | v_{i}v_{j} ∈ E(G), 1 ≤ i < j ≤ n} ⊂ ℕ, are the edge labels of G.

(6) G(A) is the total labelling of G with vertex labels A and edge labels E(A): for edge v_{i}v_{j} ∈ E(G) where 1 ≤ i < j ≤ n let its label be ℓ(v_{i}v_{j}) = k(G(A)) − a_{i} − a_{j} ∈ E(A).

(7) m(G(A)) = max{A↑, k(G(A))−P(A)↓}, is the maximum of the vertex labels and the edge labels on G(A).

Theorem 3.1 G(A) is an EMI of G with magic sum k(G(A)).

Proof. The vertex labels of G(A) are distinct, and, since A is a Gsequence, then each edge label k(G(A))−a_{i}−a_{j} is also distinct. Furthermore, since k(G(A)) ∉ A + P(A), then every k(G(A)) − a_{i} − a_{j} ∉ A, i.e., every edge label is different from every vertex label. Thus this total labelling of G is an injection into ℕ. It has magic sum k(G(A)), so is an EMI.

Example 1

Consider the graph G shown: A = (4, 5, 1, 2) is a G-sequence since all numbers in P(A) = {3, 5, 6, 7, 9} are distinct. Then P(A)↑= 9 and A + P(A) = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}. So k(G(A)) = min{[10, ∞) ∩ ({1, 2, 3} ∪ [15, ∞})=15. This gives E(A) = {6, 8, 9, 10, 12}, the edge labels on G(A). Finally A↑= 5 and P(A)↓= 3, so m(G(A)) = max{5, 15 − 3} = 12 is the largest label on G(A).

G ; •  • • •  v_{4} v_{3} v_{2} v_{1} ; V (G) = (v_{1}, v_{2}, v_{3}, v_{4})  G(A)′ ; •  • • •  21 54 ; A = (4, 5, 1, 2)  G(A)^{•  • • •  21 54}^{10} ^{8}^{6}  ^{12}^{9} A = (4, 5, 1, 2) E(A) = {6, 8, 9, 10, 12}

4 Computing κ(G), k-minimum EMI’s of G

In this section G is a fixed graph. We present an algorithm to compute κ(G), and a second algorithm to compute all witnesses for κ(G). Definition: k(G) k(G) = min{k(G(A)) | A is a G-sequence}, is the smallest value of k(G(A)) amongst all G-sequences A.

Theorem 4.1 We have κ(G) = k(G).

Proof. To see that κ(G) ≤ k(G) let X = (x_{1}, x_{2}, …, x_{n}) be a G-sequence with k(G(X)) = k(G). By Theorem 3.1 the EMI G(X) of G has magic sum k(G(X)) = k(G). Hence, by definition of κ(G), we have κ(G) ≤ k(G).

Conversely let μ be a k-minimum EMI of G, so k_{μ} = κ(G); and let A = (a_{1}, a_{2}, …, a_{n}) be the sequence of vertex labels of this G written in the same order as V (G) = (v_{1}, v_{2}, …, v_{n}). Then κ(G) − a_{i} − a_{j} for all pairs {i, j} where v_{i}v_{j} ∈ E(G) and 1 ≤ i < j ≤ n are the edge labels of this G. Since μ is an EMI then these are all distinct, hence the a_{i} + a_{j} are distinct, and so A is a G-sequence. The smallest edge label can be 1 so, κ(G) − P(A)↑≥ 1, i.e., κ(G) ≥ P(A)↑ +1. Also, if κ(G) ∈ A + P(A) then κ(G) − a_{i} − a_{j} ∈ A for some v_{i}v_{j} ∈ E(G) with 1 ≤ i < j ≤ n, thus some edge label is equal to a vertex label, a contradiction. So κ(G) ∉ A + P(A). Thus κ(G) is an integer ≥ P(A)↑ + 1 that lies outside A + P(A), but k(G(A)) is the smallest such integer. Hence κ(G) ≥ k(G(A)) ≥ k(G), since A is a G-sequence.

Combining the above paragraphs gives κ(G) = k(G).

So to compute κ(G) we will compute k(G), see Algorithm κ(G) below. Definition: W_{k}(A) Let A = (a_{1}, a_{2}, …, a_{n}) be a G-sequence.

W_{k}(A) = {W | W is a G − sequence with P(W)↑ +1 ≤ k(G(A))}.

Note that A ∈ W_{k}(A). Note also that if W ∈ W_{k}(A) then W↑≤ ⌈\frac{k(G(A))−1}{2}⌉

so |W_{k}(A)| ≤ P erm (n, ⌈\frac{k(G(A))−1}{2}⌉), the number of permutations of length

n from the set [⌈\frac{k(G(A))−1}{2}⌉]; i.e., |W_{k}(A)| is finite.

Theorem 4.2 Let A be a G-sequence. Then

k(G) = min{k(G(W)) | W ∈ W_{k}(A)}.

Proof. Let X be a G-sequence with k(G(X)) = k(G). If k(G) ≠ min{k(G(W)) | W ∈ W_{k}(A)} then X ∉ W_{k}(A), i.e., P(X)↑ +1 > k(G(A)). So k(G(X)) ≥ P(X)↑ +1 > k(G(A)), i.e., k(G) > k(G(A)), a contradiction to the minimality of k(G). Hence the result.

The following algorithm is a finite procedure for computing k(G), i.e., κ(G), it uses Theorem 4.2. Algorithm κ(G): Compute κ(G)

 (1)  Let A_{0} = (a_{1}, a_{2}, . . . , a_{n}) be a G-sequence.
 (2)  Compute k(G(A_{0})).
 (3)  List W_{k}(A_{0}) in lexicographic order.
 (4)  For each W ∈ W_{k}(A_{0}) compute k(G(W)):

IF we find W = A_{1} with k(G(A_{1})) < k(G(A_{0}))

          THEN let A_{0} = A_{1} at Step (2) and repeat

ELSE output κ(G) = k(G) = k(G(A_{0})).

Definition: k-minimum G-sequence; witness for κ(G) Let X = (x_{1}, x_{2}, …, x_{n}) be a G-sequence. Then X is a k-minimum Gsequence if k(G(X)) = κ(G); we also call X a witness for κ(G). Remark: So a ‘witness for κ(G)’ can be both a G-sequence X or the corresponding EMI G(X) of G. A Corollary of Theorem 4.1 is then:

Corollary 4.3 G-sequence X is a witness for κ(G) if and only if EMI G(X) is a witness for κ(G).

Once κ(G) is known we can find all k-minimum G-sequences, i.e., all witnesses for κ(G).

Theorem 4.4 Let X be a k-minimum G-sequence. Then all k-minimum G-sequences lie in W_{k}(X).

Proof. Let W be a k-minimum G-sequence, then k(G(W)) = κ(G). So P(W)↑ +1 ≤ k(G(W)) = κ(G) = k(G(X)), i.e., W ∈ W_{k}(X).

We give an algorithm to find all witnesses W for κ(G). For this we need:

Theorem 4.5

(i) Let μ be a k-minimum EMI of G. Then 1 ∈ ℕ appears as a label of G.

(ii) Let X = (x_{1}, x_{2}, …, x_{n}) be a k-minimum G-sequence. Then either x_{i} = 1 for some x_{i} ∈ X, or P(X)↑ +1 = κ(G), (not both).

Proof. (i) Let ℓ ∈ ℕ be the smallest label used in μ. Now define an injection μ′ : V (G) ∪ E(G) → ℕ given by μ′(w) = μ(w) − (ℓ − 1) for all w ∈ V (G) ∪ E(G). It is straightforward to check that, if ℓ > 1, then μ′ is an EMI of G with magic sum k_{μ′} = k_{μ} − 3(ℓ − 1) < k_{μ} = κ(G), a contradiction. Hence ℓ = 1 as required. (ii) Since k(G(X)) = κ(G) then the labelled graph G(X) is a k-minimum EMI of G, and so, from (i), the label 1 has been used on a vertex or an edge, (not both). If 1 is a vertex label on some v_{i} then x_{i} = 1. Or, if 1 is an edge label, then it is the smallest edge label, so 1 = k(G(X)) − P(X)↑= κ(G) − P(X)↑. That is, P(X)↑ +1 = κ(G).

Remark: See Table 3, n = 2 where both cases of Theorem 4.5(ii) are illustrated. Definition: witness(κ(G))

witness(κ(G)) = {W | W is a k−minimum G−sequence}.

We use Theorem 4.5(ii) in the following algorithm where we assume that κ(G) is known. Algorithm witness(κ(G)): Find witness(κ(G))

 (1)  Let X = (x_{1}, x_{2}, . . . , x_{n}) be a k-minimum G-sequence.

(2) List all W = (w_{1}, w_{2}, …, w_{n}) ∈ W_{k}(X) with some w_{i} = 1 or P(W)↑ +1 = κ(G), (not both).

 (3)  For these W compute k(G(W)).

IF k(G(W)) = κ(G)

          THEN output W into witness(κ(G))
          ELSE reject W.

5 Computing 𝔪(G), m-minimum EMI’s of G

In this section G is fixed. We present an algorithm to compute 𝔪(G), and a second algorithm to compute all witnesses for 𝔪(G).

Recall Definition (7) of Section 3: For a G-sequence A = (a_{1}, a_{2}, …, a_{n}) we have m(G(A)) = max{A↑, k(G(A)) − P(A)↓}. So m(G(A)) is the maximum of the vertex labels and the edge labels of G(A), i.e., the largest label of G(A). Analogous to the definition of k(G):

Definition: m(G) m(G) = min{m(G(A)) | A is a G − sequence}, is the smallest value of m(G(A)) amongst all G-sequences A.

Analogous to Theorem 4.1:

Theorem 5.1 We have 𝔪(G) = m(G).

Proof. To see that 𝔪(G) ≤ m(G) let Y = (y_{1}, y_{2}, …, y_{n}) be a G-sequence with m(G(Y)) = m(G). Now the total labelling G(Y) of G is an EMI μ of G with m_{μ} = m(G(Y)) = m(G). Hence, by definition of 𝔪(G), we have 𝔪(G) ≤ m(G).

Conversely let μ be a m-minimum EMI of G, so m_{μ} = 𝔪(G); and let A = (a_{1}, a_{2}, …, a_{n}) be the sequence of vertex labels of this G written in the same order as V (G) = (v_{1}, v_{2}, …, v_{n}). Then k_{μ} − a_{i} − a_{j} are the edge labels of this G for edges v_{i}v_{j} where 1 ≤ i < j ≤ n. As before, these are all distinct, hence the a_{i} + a_{j} are distinct, and A is a G-sequence. Now by definition of k(G(A)) we have k(G(A)) ≤ k_{μ}. So m(G(A)) = max{A↑, k(G(A)) − P(A)↓ } ≤ max{A↑, k_{μ} − P(A)↓} = m_{μ} = 𝔪(G). And then by definition of m(G), since A is a G-sequence, we have m(G) ≤ m(G(A)) ≤ 𝔪(G), as needed.

Combining the above paragraphs gives 𝔪(G) = m(G).

So, to compute 𝔪(G) we will compute m(G), see Algorithm 𝔪(G) below.

Definition: W_{m}(A) Let A = (a_{1}, a_{2}, …, a_{n}) be a G-sequence.

W_{m}(A) = {W | W is a G−sequence with W↑≤ m(G(A))}.

Note that A ∈ W_{m}(A). Note also that |W_{m}(A)| ≤ P erm (n, m(G(A))), i.e., |W_{m}(A)| is finite.

Theorem 5.2 Let A be a G-sequence. Then

m(G) = min{m(G(W)) | W ∈ W_{m}(A)}.

Proof. Let Y be a G-sequence with m(G(Y)) = m(G). If m(G) ≠ min{m(G(W)) | W ∈ W_{m}(A)} then Y ∉ W_{m}(A), i.e., Y ↑> m(G(A)). So m(G(Y)) ≥ Y ↑> m(G(A)), i.e., m(G) > m(G(A)), a contradiction to the minimality of m(G). Hence the result.

Using Theorem 5.2 we have: Algorithm 𝔪(G): Compute 𝔪(G)

 (1)  Let A_{0} = (a_{1}, a_{2}, . . . , a_{n}) be a G-sequence.
 (2)  Compute m(G(A_{0})).
 (3)  List W_{m}(A_{0}) in lexicographic order.
 (4)  For each W ∈ W_{m}(A_{0}) compute m(G(W)):

IF we find W = A_{1} with m(G(A_{1})) < m(G(A_{0}))

          THEN let A_{0} = A_{1} at Step (2) and repeat

ELSE output 𝔪(G) = m(G) = m(G(A_{0})).

Definition: m-minimum G-sequence; witness for 𝔪(G) Let Y = (y_{1}, y_{2}, …, y_{n}) be a G-sequence. Then Y is a m-minimum Gsequence if m(G(Y)) = 𝔪(G); we also call Y a witness for 𝔪(G).

Once 𝔪(G) is known we can find all m-minimum G-sequences, i.e., all witnesses for 𝔪(G).

Theorem 5.3 Let Y be a m-minimum G-sequence. Then all G-sequences with m(G(W)) = 𝔪(G) lie in W_{m}(Y).

Proof. Let W be a m-minimum G-sequence, then m(G(W)) = 𝔪(G). So W↑≤ m(G(W)) = 𝔪(G) = m(G(Y)), i.e., W ∈ W_{m}(Y).

The proof of the following Theorem is similar to the proof of Theorem 4.5. Theorem 5.4

(i) Let μ be a m-minimum EMI of G. Then 1 ∈ ℕ appears as a label of G. (ii) Let Y = (y_{1}, y_{2}, …, y_{n}) be a m-minimum G-sequence. Then either

y_{i} = 1 for some y_{i} ∈ Y or P(Y)↑ +1 = k(G(Y)), (not both). Remark: See Table 3, G = K_{2}, where both cases of Theorem 5.4(ii) are illustrated. Theorem 5.4(ii) gives us a quick method to compute k(G(Y)) for a m-minimum G-sequence Y when 1 ∉ Y. Definition: witness(𝔪(G))

witness(𝔪(G)) = {W | W is a m−minimum G−sequence}. We use Theorem 5.4(ii) in the following algorithm where we assume that

𝔪(G) is known.

Algorithm witness(𝔪(G)): Find witness(𝔪(G))

 (1)  Let Y = (y_{1}, y_{2}, . . . , y_{n}) be a m-minimum G-sequence.

(2) List all W = (w_{1}, w_{2}, …, w_{n}) ∈ W_{m}(Y) with some w_{i} = 1 or P(Y)↑ +1 = k(G(W)), (not both).

 (3)  For these W compute m(G(W)).

IF m(G(W)) = 𝔪(G)

          THEN output W into witness(𝔪(G))
          ELSE reject W.

6 Results for G with n = 2, 3, …, 7, double-witnesses

In this section, for a fixed graph G with n = 2, 3, …, 7 vertices we present our results from Algorithm κ(G) and Algorithm 𝔪(G). (For a typical fixed G, the witnesses from Algorithm witness(κ(G)) and Algorithm witness(𝔪(G)) are too numerous to list.)

All the 1252 simple graphs G with up to 7 vertices are listed and numbered as G1, G2, ⋯, G1252 in Read and Wilson [10]. We use this numbering system, and for graph G# we compute the quadruple: (G#, κ(G#), 𝔪(G#), def(G#)).

Definitions: (k, m)-minimum G-sequence; double-witness, (k, m)-minimum EMI of G; double-witness, double−witness(G)

(1) Let A = (a_{1}, a_{2}, …, a_{n}) be a G-sequence. Then A is a (k, m)-minimum G-sequence if both k(G(A)) = κ(G) and m(G(A)) = 𝔪(G); we also call A a double-witness.

(2) Let μ be an EMI of G. Then μ is a (k, m)-minimum EMI of G if both k_{μ} = κ(G) and m_{μ} = 𝔪(G); we also call μ a double-witness.

(3) double−witness(G) = {W | W is a (k, m)−minimum G−sequence}.

Algorithm double-witness(G): Find double−witness(G)

For each X ∈ witness(κ(G)) compute m(G(X)).

IF m(G(X)) = 𝔪(G)

THEN output X into double−witness(G)

          ELSE reject X.

Remark: If G-sequence A is a double-witness we use bold numbers in A.

•  • 1 ^{3} 2 (G3, 6, 3, 0) (1, 2)  • • • 1_{5} 2  _{4} 3 (G6, 8, 5, 0) (1, 2, 3)  • • • 1_{6} 2  _{5} 3_{4} (G7, 9, 6, 0) (1, 2, 3)

•  • 1 ^{7} 3 •  • 2 _{5} 4 (G11, 11, 7, 1) (1, 2, 4, 3)  • • • •2^{7} 1_{6} 3  _{5} 4 (G13, 10, 7, 0) (2, 1, 3, 4)  • •  • • 1 ^{6} 4_{5} 3_{7}  2 (G14, 11, 7, 0) (1, 3, 2, 4)

• • • •3^{7} 1_{8} 2  _{6} 4_{5} (G15, 11, 8, 0) (3, 1, 2, 4)  • •  • • 1 ^{5} 6_{4}2_{7} 3_{8} (G16, 12, 8, 0) (1, 3, 2, 6)  • •  • •^{7} 1 ^{8} 3_{5}4_{6} 2_{9} (G17, 12, 9, 0) (1, 2, 4, 3)  • •  • •^{10} ^{7} 1 ^{8} 5_{6}3_{9} 2_{11} (G18, 14, 11, 1) (1, 2, 3, 5)

Figure 2: All graphs G with n = 2, 3, or 4 vertices. Each G is labelled with a (k, m)-minimum EMI. Below G is its (G, κ(G), 𝔪(G), def(G))-quadruple, and the (k, m)-minimum G-sequence (double-witness) consisting of the vertex labels. The smallest graph G without an EMTL (def(G) > 0) is G11 = 2K_{2}, the second smallest is G18 = K_{4}.

(G26, 13, 8, 0) (G29, 12, 9, 0) (G30, 13, 9, 0) (G31, 13, 9, 0)
(G32, 14, 10, 1) (G34, 13, 10, 0) (G35, 13, 10, 0) (G36, 14, 10, 0)
(G37, 14, 10, 0) (G38, 14, 10, 0) (G40, 14, 11, 0) (G41, 14, 11, 0)
(G42, 14, 11, 0) (G43, 14, 11, 0) (G44, 15, 11, 0) (G45, 15, 12, 0)
(G46, 15, 12, 0) (G47, 15, 12, 0) (G48, 15, 12, 0) (G49, 16, 13, 0)
(G50, 16, 13, 0) (G51, 17, 14, 0) (G52, 18, 15, 0)

Table 1. The (G, κ(G), 𝔪(G), def(G))-quadruple for the 23 graphs G on n = 5 vertices.

(G61, 15, 9, 0) (G68, 15, 11, 1) (G69, 15, 10, 0) (G70, 15, 10, 0)
(G77, 14, 11, 0) (G78, 15, 11, 0) (G79, 15, 11, 0) (G80, 15, 11, 0)
(G81, 15, 11, 0) (G82, 15, 11, 0) (G83, 16, 11, 0) (G84, 16, 12, 1)
(G85, 16, 11, 0) (G92, 15, 12, 0) (G93, 15, 12, 0) (G94, 15, 12, 0)
(G95, 15, 12, 0) (G96, 16, 12, 0) (G97, 16, 12, 0) (G98, 16, 12, 0)
(G99, 16, 12, 0) (G100, 16, 12, 0) (G101, 16, 12, 0) (G102, 16, 12, 0)
(G103, 16, 12, 0) (G104, 16, 12, 0) (G105, 17, 12, 0) (G106, 18, 13, 1)
(G111, 16, 13, 0) (G112, 16, 13, 0) (G113, 16, 13, 0) (G114, 16, 13, 0)
(G115, 17, 13, 0) (G116, 17, 14, 1)^{∗} (G117, 16, 13, 0) (G118, 16, 13, 0)
(G119, 16, 13, 0) (G120, 16, 13, 0) (G121, 17, 13, 0) (G122, 16, 13, 0)
(G123, 17, 13, 0) (G124, 16, 13, 0) (G125, 17, 13, 0) (G126, 17, 13, 0)
(G127, 17, 13, 0) (G128, 17, 13, 0) (G129, 17, 13, 0) (G130, 18, 13, 0)
(G133, 18, 15, 1) (G134, 17, 14, 0) (G135, 17, 14, 0) (G136, 17, 14, 0)
(G137, 17, 14, 0) (G138, 17, 14, 0) (G139, 17, 14, 0) (G140, 17, 14, 0)
(G141, 17, 14, 0) (G142, 17, 14, 0) (G143, 18, 15, 1)^{∗} (G144, 17, 14, 0)
(G145, 17, 14, 0) (G146, 18, 14, 0) (G147, 17, 14, 0) (G148, 17, 14, 0)
(G149, 17, 14, 0) (G150, 18, 14, 0) (G151, 17, 14, 0) (G152, 18, 14, 0)
(G153, 18, 14, 0) (G154, 18, 14, 0) (G156, 18, 15, 0) (G157, 18, 15, 0)
(G158, 18, 15, 0) (G159, 18, 15, 0) (G160, 18, 15, 0) (G161, 18, 15, 0)
(G162, 18, 15, 0) (G163, 18, 15, 0) (G164, 18, 15, 0) (G165, 18, 15, 0)
(G166, 18, 15, 0) (G167, 18, 15, 0) (G168, 18, 15, 0) (G169, 18, 15, 0)
(G170, 18, 15, 0) (G171, 18, 15, 0) (G172, 18, 15, 0) (G173, 18, 15, 0)
(G174, 18, 15, 0) (G175, 19, 15, 0) (G177, 19, 16, 0) (G178, 19, 16, 0)
(G179, 19, 16, 0) (G180, 19, 16, 0) (G181, 19, 16, 0) (G182, 19, 16, 0)
(G183, 19, 16, 0) (G184, 19, 16, 0) (G185, 19, 16, 0) (G186, 19, 16, 0)
(G187, 19, 16, 0) (G188, 19, 16, 0) (G189, 19, 16, 0) (G190, 20, 17, 1)
(G191, 20, 17, 0) (G192, 20, 17, 0) (G193, 20, 17, 0) (G194, 20, 17, 0)
(G195, 21, 17, 0) (G196, 20, 17, 0) (G197, 20, 17, 0) (G198, 20, 17, 0)
(G199, 20, 17, 0) (G200, 21, 18, 0) (G201, 22, 19, 1) (G202, 21, 18, 0)
(G203, 21, 18, 0) (G204, 22, 19, 1) (G205, 22, 19, 0) (G206, 22, 19, 0)
(G207, 23, 20, 0) (G208, 25, 21, 0)

Table 2. The (G, κ(G), 𝔪(G), def(G))-quadruple for the 122 graphs G on n = 6 vertices.

Remark: In Table 2 the two graphs G116 and G143 marked with a ^{∗} each have def(G) = 1; thus we have found two new graphs G on 6 vertices with def(G) = 1. See the incomplete list of 7 graphs G on 6 vertices with def(G) = 1 in [5]; the complete list is {G68, G84, G106, G116, G133, G143, G190, G201, G204}. Graph G116 is K_{2} ∪ K_{4}: we have also confirmed that G116 does not have an EMTL (def(G116) > 0) by exhaustive search without the aid of a computer. Graph G143 has 8 edges and odd degrees [1, 3, 3, 3, 3, 3] so we may also use Theorem 1 of Ringel and Llado [11] to confirm that G143 does not have an EMTL.

•  • 4 ^{7} 6 •  • • •  25 31 ^{11} ^{12}^{14}_{9}_{13}  _{10} (G116, 17, 14, 1)  ^{2 136 5  4^{15}^{12}  ^{13}^{10} ^{11}^{7}  ^{8}^{9}^{• •  • • • •} (G143, 18, 15, 1)} ^{•  •  • 3 ^{11} 1 ^{10} 4 •  •  • 5 ^{8} 2 ^{7} 6 k(G) = 15 m(G(A)) = 11 •  •  • 1 ^{8} 7 ^{6} 3 •  •  • 4 _{10} 2 _{9} 5 k(G(A)) = 16 m(G) = 10 (G70, 15, 10, 0)}

Figure 3: Two new graphs G on 6 vertices each with def(G) = 1; G = 2P_{3}, the smallest graph without a double witness, first a k-minimum EMI and then a m-minimum EMI are shown. (The m-minimum EMI is an EMTL.)

Remark: A graph may have a large number of double-witnesses, eg., graph G77 on 6 vertices has 3840 double-witnesses. The smallest graph without a double-witness is G70 = 2P_{3}, and the next smallest is G79 = B_{2,2}. Both these graphs G have an EMTL and satisfy 15 = κ(G) < κ_{EMT L}(G) = 16, see Figs. 1 and 3. The smallest graph without both a double-witness and an EMTL is G106 = 2K_{3}.

Theorem 6.1 Let G have an EMTL. Then G has a double-witness if and only if κ(G) = κ_{EMT L}(G).

Proof. Graph G has an EMTL so 𝔪(G) = n + e.

For the forward implication: Let Z be a double-witness for G. So m(G(Z)) = 𝔪(G) = n + e, i.e., G(Z) is an EMTL. Thus κ_{EMT L}(G) ≤ k(G(Z)) = κ(G). Hence, from Equation (1), κ(G) = κ_{EMT L}(G).

For the backward implication: Let X be a witness for κ_{EMT L}(G), then k(G(X)) = κ_{EMT L}(G) = κ(G). Also, since G(X) is an EMTL, m(G(X)) = n + e = 𝔪(G). That is, X is a double-witness for G.

We have a countable class of graphs without a double-witness:

Corollary 6.2 For even n ≥ 4 the bi-star B_{\frac{n−2}{2} , \frac{n−2}{2}} does not have a double-witness.

Proof. From the Remark after Theorem 2.4 we have κ(B_{\frac{n−2}{2} , \frac{n−2}{2}} ) < κ_{EMT L}(B_{\frac{n−2}{2} , \frac{n−2}{2}} ), the contrapositive of Theorem 6.1 then gives the result.

Note: A file containing the (G, κ(G), 𝔪(G), def(G))-quadruples for the 888 graphs G on n = 7 vertices is available from the authors. As is a file containing the (T, κ(T), 𝔪(T), def(T))-quadruples for the 200 trees T on up to n = 10 vertices.

7 G = K_{n}, Well Spread-sequences

When G = K_{n} a G-sequence is a Well Spread-sequence, a WS-sequence; see Kotzig [4], and [6].

An upperbound for both κ(K_{n}) and 𝔪(K_{n}) due to Wood [15] is:

κ(K_{n}), 𝔪(K_{n}) ≤ (3 + o(1))n^{2},

and an upperbound for κ(K_{n}) due to Pikhurko [9] is:

κ(K_{n}) ≤ (2.38... + o(1))n^{2}.

Lower bounds for κ(K_{n}) and 𝔪(K_{n}) are given at the end of this section in Theorem 7.6.

We first complete our discussion of graphs G from Theorem 1.1 by dealing with line 1:

Theorem 7.1 We have κ(K_{n}) = κ_{EMT L}(K_{n}) for n ∈ {2, 3, 5, 6}.

Proof. For each n ∈ {2, 3, 5, 6} compare the value of κ(K_{n}) in Section 6 to the value of κ_{EMT L}(K_{n}) in Theorem 1.1.

Definition: dual of A Let A = (a_{1}, a_{2}, …, a_{n}) be a WS-sequence. The dual of A is the WS-sequence A′ = (m(K_{n}(A)) + 1 − a_{n}, m(K_{n}(A)) + 1 − a_{n−1}, …, m(K_{n}(A)) + 1 − a_{1}).

n κ(K_{n}) W ∈ witness(κ(K_{n})) 𝔪(K_{n}) W ∈ witness(𝔪(K_{n})), W′  def(K_{n})
1 1  1  0
2 6 (1, 2)  3^{∗} (1, 2)^{∗}, (2, 3)^{∗}  0
(1, 3)  (1, 3)^{∗}, (1, 3)^{∗}

(2, 3)

3 9 (1, 2, 3) 6^{∗} (1, 2, 3)^{∗}, (4, 5, 6)^{∗} 0

(1, 3, 5)^{∗}, (2, 4, 6)^{∗}

4 14 (1, 2, 3, 5) 11^{∗} (1, 2, 3, 5), (7, 9, 10, 11) 1
(1, 2, 3, 7)  (1, 2, 3, 7), (5, 9, 10, 11)
(1, 2, 4, 7)  (1, 2, 4, 7), (5, 8, 10, 11)

(1, 3, 4, 5), (7, 8, 9, 11) (1, 3, 5, 8), (4, 7, 9, 11) (1, 4, 5, 9), (3, 7, 8, 11) (1, 6, 7, 8), (4, 5, 6, 11) (1, 6, 7, 9), (3, 5, 6, 11) (2, 3, 6, 9), (3, 6, 9, 10) (2, 4, 6, 10), (2, 6, 8, 10)

5 18 (1, 2, 3, 5, 9) 15^{∗} (1, 2, 3, 5, 9)^{∗}, (7, 11, 13, 14, 15)^{∗} 0

(1, 8, 9, 10, 12)^{∗∗}, (4, 6, 7, 8, 15)^{∗∗}

6 25 (1, 3, 4, 5, 9, 14) 21^{∗} (1, 3, 4, 5, 9, 14)^{∗}, (8, 13, 17, 18, 19, 21)^{∗} 0
(1, 2, 3, 5, 8, 13)  (2, 6, 7, 8, 10, 18)^{∗∗}, (4, 12, 14, 15, 16, 20)^{∗∗}

Table 3. Values of κ(K_{n}), 𝔪(K_{n}), and def(K_{n}) for 1 ≤ n ≤ 6, and all witnesses.

Remark: In Table 3 the values and sequences marked ^{∗} first appeared in Kotzig and Rosa [5] and [6], and the sequences marked ^{∗∗} first appeared in Section 7.1 of [14], see also Section 2.3.3 of [13]. All remaining values and sequences are new. (The sequence (8, 13, 17, 18, 19, 21) was printed erroneously with the ‘13’ as ‘11’ in both [14] and [13].) As before, double-witnesses appear in bold. Note that the m-minimum WS-sequences appear in W, W′ pairs.

n κ(K_{n}) W ∈ witness(κ(K_{n}))  𝔪(K_{n}) W ∈ witness(𝔪(K_{n})), W′  def(K_{n})
7  38 (1, 2, 3, 5, 8, 13, 21)  32 (3, 4, 5, 7, 10, 15, 23), (10, 18, 23, 26, 28, 29, 30)  4

(1, 4, 5, 7, 9, 14, 21)

8 51 (2, 3, 4, 6, 11, 16, 22, 28) 46 (2, 3, 4, 6, 11, 16, 22, 28), (19, 25, 31, 36, 41, 43, 44, 45) 10

(3, 5, 6, 7, 11, 16, 23, 30), (17, 24, 31, 36, 40, 41, 42, 44)

9 71 (1, 2, 3, 5, 9, 15, 20, 29, 38) 64 (1, 10, 11, 12, 14, 19, 27, 33, 39), (26, 32, 38, 46, 51, 53, 54, 55, 64) 19
(2, 3, 4, 6, 12, 17, 22, 29, 41)  (2, 10, 12, 13, 14, 18, 27, 34, 41), (24, 31, 38, 47, 51, 52, 53, 55, 63)

(3, 5, 6, 7, 11, 16, 25, 32, 39), (26, 33, 40, 49, 54, 58, 59, 60, 62) (10, 12, 13, 14, 18, 23, 32, 39, 46), (19, 26, 33, 42, 47, 51, 52, 53, 55) (12, 13, 14, 16, 20, 26, 31, 36, 52), (13, 29, 34, 39, 45, 49, 51, 52, 53)

10 89 (1, 2, 3, 5, 9, 16, 25, 30, 35, 47) 86 (1, 2, 3, 5, 9, 16, 25, 30, 35, 47), (40, 52, 57, 62, 71, 78, 82, 84, 85, 86)  31

(2, 8, 9, 10, 14, 18, 28, 31, 42, 53), (34, 45, 56, 59, 69, 73, 77, 78, 79, 85) (6, 10, 14, 15, 22, 24, 35, 38, 41, 60), (27, 46, 49, 52, 63, 65, 72, 73, 77, 81) (13, 14, 15, 20, 26, 29, 39, 43, 47, 65), (22, 40, 44, 48, 58, 61, 67, 72, 73, 74)

11 116 (2,3,4,11,26,29,39,43,49,55,60) 110^{†} (6, 7, 8, 10, 14, 21, 30, 35, 40, 52, 70)^{††}, (41, 59, 71, 76, 81, 90, 97, 101, 103, 104, 105) 44
12 140–154  137–150  59–72

Table 4. Values of κ(K_{n}), 𝔪(K_{n}), and def(K_{n}) for 7 ≤ n ≤ 11, and all witnesses, except for the value 𝔪(K_{11}) = 110 where the sequence marked ^{††} is unlikely to be the only witness; a large portion of the search space was left unsearched. For n = 12 we give lower and upper bounds; see below.

Remark: In Table 4 for 𝔪(K_{11}) = 110^{†} see the comments involving ρ^{∗}(n) below. We have answered Research Problem 2.2 in Section 2.3.4 of [13] which asks to find 𝔪(K_{7}) and 𝔪(K_{8}).

If A = (a_{1}, a_{2}, …, a_{n}) is a WS-sequence then without loss of generality we let 1 ≤ a_{1} < a_{2} < ⋯ < a_{n}. Thus, see Definitions (4) and (7) of Section 3, we have:

k(K_{n}(A)) ≥ a_{n−1}+a_{n}+1 and m(K_{n}(A)) = max{a_{n}, k(K_{n}(A))−a_{1}−a_{2}}. (3)

Definitions: ρ(A), ρ^{∗}(n) (See [4] and [6].)

(1) Let A = (a_{1}, a_{2}, …, a_{n}) be a WS-sequence. Then ρ(A) = a_{n} + a_{n−1} − a_{2} − a_{1} + 1 is the span of pairwise sums of A.

(2) ρ^{∗}(n) = min{ρ(A) | A is a WS-sequence of length n}, is the smallest ρ(A) amongst all WS-sequences A of length n.

Theorem 7.2 Let A = (a_{1}, a_{2}, …, a_{n}) be a WS-sequence. Then

(i) m(K_{n}(A)) ≥ ρ(A),

(ii) 𝔪(K_{n}) ≥ ρ^{∗}(n).

Proof. (i) Using Equation (3) twice gives m(K_{n}(A)) ≥ k(K_{n}(A)) − a_{1} − a_{2} ≥ a_{n−1} + a_{n} + 1 − a_{1} − a_{2} = ρ(A). For (ii) let Y be a WS-sequence with m(K_{n}(Y)) = 𝔪(K_{n}). Then 𝔪(K_{n}) = m(K_{n}(Y)) ≥ ρ(Y) ≥ ρ^{∗}(n).

Remark: For n = 2, 3, …, 8 the values of ρ^{∗}(n) were first computed by hand in [4]; these values were verified by computer and extended to n = 12 in [8], see also Section 2.3.4 of [13]. In particular, ρ^{∗}(11) = 110. As mentioned in the caption for Table 4 and the Remark following Table 4, for n = 11 the WS-sequence A = (6, 7, 8, 10, 14, 21, 30, 35, 40, 52, 70)^{††} has m(K_{11}(A)) = 110, thus 𝔪(K_{11}) ≤ 110. But from Theorem 7.2(ii) we have 𝔪(K_{11}) ≥ ρ^{∗}(11) = 110. Thus 𝔪(K_{11}) = 110 as given in Table 4. The inequality of Theorem 7.2(ii) is tight for n = 11.

Definitions: σ(A), σ^{∗}(n) (See [4] and [6].)

(1) Let A = (a_{1}, a_{2}, …, a_{n}) be a WS-sequence. Then σ(A) = a_{n} − a_{1} + 1 is the span of A.

(2) σ^{∗}(n) = min{σ(A) | A is a WS-sequence of length n}, is the smallest σ(A) amongst all WS-sequences A of length n.

Remark: As for ρ^{∗}(n), for n = 2, 3, …, 8 values of σ^{∗}(n) first appeared in [4]; and were extended to n = 12 in [8].

Lemma 7.3 Let A = (a_{1}, a_{2}, …, a_{n}) be a WS-sequence. Then a_{i} ≥ σ^{∗}(i) for each i = 1, 2, …, n.

Proof. For each i = 1, 2, …, n consider the WS-sequence A_{i} = (a_{1}, a_{2}, …, a_{i}). We have σ(A_{i}) = a_{i} − a_{1} + 1 ≥ σ^{∗}(i). So a_{i} ≥ σ^{∗}(i) + a_{1} − 1. But a_{1} ≥ 1, and hence the result.

Theorem 7.4 We have κ(K_{n}) ≥ σ^{∗}(n − 1) + σ^{∗}(n) + 1.

Proof. Let X = (x_{1}, x_{2}, …, x_{n}) be a WS-sequence with k(K_{n}(X)) = κ(K_{n}). Using Equation (3) then Lemma 7.3, we have κ(K_{n}) = k(K_{n}(X)) ≥ x_{n−1} + x_{n} + 1 ≥ σ^{∗}(n − 1) + σ^{∗}(n) + 1.

Theorem 7.5 We have κ(K_{n}) ≥ 𝔪(K_{n}) + 3.

Proof. Let μ be a k-minimum EMI of K_{n}, i.e., k_{μ} = κ(K_{n}), with largest label m_{μ} ≥ 𝔪(K_{n}). Whether label m_{μ} is on a vertex or edge, the magic sum k_{μ} is the sum of this label and two other labels. Hence κ(K_{n}) = k_{μ} ≥ m_{μ} + 1 + 2 ≥ 𝔪(K_{n}) + 3.

Note: From Theorem 7.2(ii) and [8] we have 𝔪(K_{12}) ≥ ρ^{∗}(12) = 137. And then from Theorem 7.5 we have κ(K_{12}) ≥ 𝔪(K_{12}) + 3 ≥ 140. The WSsequence S = (1, 3, 5, 6, 9, 21, 32, 41, 51, 58, 65, 79) has k(K_{12}(S)) = 154 and m(K_{12}(S)) = 150. Thus κ(K_{12}) ≤ 154 and 𝔪(K_{12}) ≤ 150.

Hence 140 ≤ κ(K_{12}) ≤ 154 and 137 ≤ 𝔪(K_{12}) ≤ 150 as given in Table 4.

We finish this section with lower bounds for κ(K_{n}) and 𝔪(K_{n}):

Theorem 7.6 For n ≥ 13, we have

(i) κ(K_{n}) ≥ n^{2} − 4n + 13,

(ii) 𝔪(K_{n}) ≥ n^{2} − 5n + 14.

Proof. (i) From [4] we have σ^{∗}(n) ≥ 4 + \binom{n−1}{2}; Theorem 7.4 then gives the result. (ii) Also from [4] we have ρ^{∗}(n) ≥ n^{2} − 5n + 14; Theorem 7.2(ii) then gives the result.

8 Miscellaneous

Comment on algorithms: The first four algorithms presented in this paper each include an operation which lists the G-sequences in the sets W_{k}(A), or W_{m}(A), in lexicographical order. Then each G-sequence is evaluated to determine if it produces an equal, or smaller, value as the presently smallest known value, for k(G(A)), or m(G(A)), or if it is a witness for κ(G), or for 𝔪(G). The actual software implementations of these algorithms do not follow these instructions exactly as it proved much easier to simply generate (and evaluate) all reasonable G-sequences while maintaining which ones are currently the best, and then reporting the final results once the entire set of reasonable G-sequences has been exhausted. This brute force enumeration strategy is one whose efficiency is greatly improved by the known bounds for σ^{∗}(i), which denotes the smallest that the i-th term of any WS-sequence of length at least i can be, see Lemma 7.3. Three new integer sequences: Tables 3 and 4 provide us with three integer sequences that do not appear in the On-Line Encyclopedia of Integer Sequences, Sloane [12]. We have sent the first 11 terms of each sequence to [12]. They are: {κ(K_{n}) | n ≥ 1} = {1, 6, 9, 14, 18, 25, 38, 51, 71, 89, 116, …}, {𝔪(K_{n}) | n ≥ 1} = {1, 3, 6, 11, 15, 21, 32, 46, 64, 86, 110, …}, and {def(K_{n}) | n ≥ 1} = {0, 0, 0, 1, 0, 0, 4, 10, 19, 31, 44, …}. Further Research and Questions:

(1) Determine the exact values of κ(K_{12}) and 𝔪(K_{12}); and extend Table 4 for n ≥ 13.

(2) For every even n ≥ 2 does K_{n} have a double-witness? It does for n = 2, 4, 6, 8, and 10.

(3) For n = 2, 3, 4, 5, and 6 the following is true: κ(G) < κ(K_{n}) and 𝔪(G) < 𝔪(K_{n}), for all G ≠ K_{n}. Is it true for all n?

(4) Find κ(G) and 𝔪(G) for other graphs G, and for graphs G_{n} ∈ G for a class of graphs G. In particular, for classes G whose members have an EMTL; eg., G = \{K_{\frac{n}{2} , \frac{n}{2}} | n even and ≥ 2\}, and G = \{K_{m,n} | m, n ≥ 1\}. See [2] for many other such classes.

(5) For G_{n} ∈ G investigate the quantity κ_{EMT L}(G_{n})−κ(G_{n}). Can κ_{EMT L}(G_{n})− κ(G_{n}) > cn^{2}, for some constant c > 0 and for sufficiently large n? See the Remark after Theorem 2.4.

(6) Improve the lower bounds on κ(K_{n}) and 𝔪(K_{n}), see Theorem 7.6.

References

[1] S.Avadayappan, R.Vasuki, P.Jeyanthi. Magic Strength of a Graph, Indian. J. Pure. Appl. Math. 31, no.7, 873–883, (2000).

[2] J.A.Gallian. A Dynamic Survey of Graph Labelling. Electronic J. Comb. 5, Dynamic Survey, DS6. (2005).

[3] M.C.Kong, S-M.Lee, S.H.Sun. On Magic Strength of a Graph. Ars. Combin. 45, 193–200, (1997).

[4] A.Kotzig. On Well Spread Sets of Integers. Publ. CRM -161, (1972).

[5] A.Kotzig, A.Rosa. Magic Valuations of Finite Graphs. Canad. Math. Bull. 13, 451–461, (1970).

[6] A.Kotzig, A.Rosa. Magic Valuations of Complete Graphs. Publ. CRM - 175, (1972).

[7] M.Murugan. Almost-Magic, Relaxed-Magic and Magic Strength of a Graph. Util. Math. 65, 53–64, (2004).

[8] N.C.K.Phillips, W.D.Wallis. Well-Spread Sequences. J. Combin. Math. Combin. Comput. 31, 91–96, (1999).

[9] O.Pikhurko. Dense Edge-Magic Graphs and Thin Additive Bases. Disc. Math. 306, 2097–2107, (2006).

[10] R.C.Read, R.J.Wilson. An Atlas of Graphs, Oxford University Press, (2004).

[11] G.Ringel, A.S.Llado. Another Tree Conjecture. Bull. Inst. Combin. Appl. 18, 83–85, (1996).

[12] N.J.A.Sloane. The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/∼njas/sequences/

[13] W.D.Wallis. Magic Graphs, Birkhäuser, (2001).

[14] W.D.Wallis, E.T.Baskoro, M.Miller, Slamin. Edge-Magic Total Labelings. Australas. J. Comb. 22, 177–190, (2000).

[15] D.R.Wood. On Vertex-Magic and Edge-Magic Total Injections of Graphs. Australas. J. Comb. 26, 49–63, (2002).