Totally Magic Injections of Graphs

John P. McSorley Department of CCTM London Metropolitan University 100 Minories, London EC3N 1JY mcsorley60@hotmail.com

Abstract

For a simple graph G consider an injection μ: V ∪ E → ℕ. If for every vertex x ∈ V we have μ(x) + ∑_{y∼x} μ(xy) = h, and for every edge xy ∈ E we have μ(x) + μ(xy) + μ(y) = k, for some constants h and k, then μ is a totally magic injection (TMI) of G. Also, m_{t}(G) is the smallest number in ℕ such that there is a TMI μ: V ∪ E → {1, 2, …, m_{t}(G)}. Here we study TMIs and the number m_{t}(G) for certain G. One theorem, the Star Theorem, is useful for eliminating many classes of well-known graphs that could have a TMI. For most n and n_{j} the following graphs do not have a TMI: every non-star tree, P_{n}, C_{n}, W_{n}, K_{n}, and K_{n_{1},n_{2},...,n_{p}}. We determine m_{t}(F) for every forest F that has a TMI, and m_{t}(G) for every graph G with ≤ 6 vertices that has a TMI.

1 Totally Magic Injections

Let G be a simple graph with set of vertices V (G) or V of size v, and set of edges E(G) or E of size e. We use single letters for vertices, eg. x, and pairs of letters for edges, eg. xy. The notation x ∼ y indicates that x is adjacent to y. The degree of a vertex x is deg(x). Let ℕ = {1, 2, …} denote the natural numbers and let [m] = {1, 2, …, m}.

Consider an injection

μ: V ∪ E → ℕ,

i.e., each vertex and edge of G is labeled with a distinct natural number. For a vertex x ∈ V let its weight under μ be wt(x):

wt(x) = μ(x) + ∑_{y∼x} μ(xy),

and for an edge xy ∈ E let its weight under μ be wt(xy):

wt(xy) = μ(x) + μ(xy) + μ(y).

Then μ is a totally magic injection (TMI) of G if for every vertex x ∈ V and for every edge xy ∈ E we have

wt(x) = h and wt(xy) = k,

for some constants h and k.

Comparing with the definition of a totally magic labeling (TML) from [2] in which the labeling is λ: V ∪ E → {1, 2, …, v + e}, we see that our definition of a totally magic injection is a generalization of this. We use the symbol μ for a TMI to distinguish it from the usual symbol λ for a TML.

The study of graphs with a TMI is an interesting question in its own right. Also, by weakening the definition of a TML to a TMI, we hope to shed further light on the features of a graph with a TML, since every component of a graph with a TML must have a TMI, see §2.

We call h the vertex constant of μ, and k the edge constant. When necessary we use wt_{μ}, h_{μ},... for wt, h,... to signify μ.

Suppose that in a TMI μ of G the largest label is m, then we call μ a [m]-totally magic injection, a [m]-TMI. We call m the size of the injection. A [m]-TMI of G is minimal if G does not have a [m′]-TMI for every m′ < m. Such a TMI is a minimal TMI or a minimal [m]-TMI.

We define m_{t}(G) to be the smallest m such that G has a [m]-TMI. Clearly m_{t}(G) ≥ v + e and a TML from [2] is a minimal TMI or a minimal [v + e]- TMI. We also define the total deficiency of G, def_{t}(G), to be m_{t}(G) − v − e. If G has a TML then m_{t}(G) = v + e and def_{t}(G) = 0.

This concludes §1. In §2 we give examples of graphs with and without a TMI. We also prove the first useful Theorems. In §3 we prove the Star Theorem which gives many ‘forbidden configurations’ that prevent a graph from having a TMI. Using these forbidden configurations we eliminate many classes of well-known graphs that could have a TMI. In §4 we determine m_{t}(F) for every forest F that has a TMI. Finally, in §5, we define a TMIsurvivor, and determine m_{t}(G) for every graph G with ≤ 6 vertices that has a TMI.

2 Examples, First Theorems

If, for a graph G, an injection μ: V ∪ E → ℕ satisfies wt(x) = h for a fixed h for all vertices x ∈ V then μ is a vertex-magic injection of G. See §3.9 of [5], where it is shown that all graphs except those with K_{1}∪K_{1} as components or a K_{2} component have a vertex-magic injection. Similarly, if wt(xy) = k for a fixed k for all edges xy ∈ E then μ is an edge-magic injection of G. See §2.10 of [5], where it is shown that all graphs have an edge-magic injection. Thus a TMI of G is both a vertex-magic injection and an edge-magic injection. So, perhaps not surprisingly, graphs that have a TMI appear to be rare. In fact, (see §5), amongst the 208 graphs with ≤ 6 vertices, exactly 174 have a vertex-magic injection, all 208 have an edge-magic injection, but only 12 have a TMI.

Example 1 Four graphs. The first three have a TMI, the fourth does not.

[figure: 1; K_{1}; (i); 1; 8; 6; 7; 2; 4; 3; K_{1,3}; (ii); 5; 4; 6; 1; 2; 3; K_{3}; (iii); K_{2}; (iv)]

(i) The isolated vertex K_{1}. Here v = h = m = m_{t}(K_{1}) = 1, and e = def_{t}(K_{1}) = 0. If we let K_{1} = {x} then we see that, for any fixed h ∈ ℕ, the injection given by: μ(x) = h is a TMI of K_{1}. Hence a given graph can have different TMIs.

(ii) The star K_{1,3}. Here v = 4, e = 3, h = 10, k = 11, and m = 8. This is the smallest m possible for a TMI of K_{1,3} because m_{t}(K_{1,3}) ≥ v+e = 7, but a [7]-TMI of K_{1,3} would be a TML and K_{1,3} does not have a TML, see Corollary 3.2 of [2]. So this [8]-TMI of K_{1,3} is a minimal TMI, thus m_{t}(K_{1,3}) = 8 and def_{t}(K_{1,3}) = 1.

(iii) The triangle K_{3}. Here v = e = 3, h = 9, k = 12, and m = v + e = 6. So this [6]-TMI of K_{3} is a TML, a minimal TMI, thus m_{t}(K_{3}) = 6 and def_{t}(K_{3}) = 0.

(iv) The isolated edge K_{2}. Call this edge xy. If it has a TMI μ then we must have wt(x) = μ(x) + μ(xy) = wt(y) = μ(y) + μ(xy), i.e., μ(x) = μ(y). This is a contradiction because μ is an injection. So K_{2} doesn’t have a TMI.

The following Lemma will be useful in this paper.

Lemma 2.1 Let G have a [m]-TMI with vertex constant h. Then

(i) h ≥ m,

(ii) h = m if and only if G has an isolate.

Proof. (i) Let μ denote the [m]-TMI of G, so m has been used either as a vertex label or as an edge label in G. Suppose that m has been used as a vertex label on vertex x, so μ(x) = m. Then h = wt(x) = μ(x) + ∑_{y∼x} μ(xy) = m + ∑_{y∼x} μ(xy) ≥ m. Now suppose that m has been used as an edge label on edge xz, so μ(xz) = m. Then h = wt(x) = μ(x) + m +

∑_{y≠z^{y∼x}} μ(xy) > m since μ(x) > 0, so h ≥ m also.

(ii) From (i) if h = m then m must have been a vertex label, at vertex x say. Then h = m if and only ∑_{y∼x} μ(xy) = 0, if and only if x is an isolate.

As usual, in the remainder of this section G is an arbitrary simple graph.

Theorem 2.2 Let G have a TMI. Then every component of G has a TMI.

Proof. Let G have a TMI μ, and let C be any component of G. Then clearly the ‘restriction’ of μ to C is a TMI of C.

The converse of this Theorem is not true. Consider the graph H = K_{1} ∪ K_{1} = {x} ∪ {y}, the union of two isolates. From Lemma 2.1(ii) if H has a [m]-TMI μ then both isolates in H must receive the label m. This is a contradiction because μ is an injection, so H doesn’t have a TMI. Although this is a simple example it shows that, in general, a TMI of H_{1} and a TMI of H_{2} cannot necessarily be ‘pieced together’ to produce a TMI of H_{1} ∪ H_{2}. This example also shows that if G has K_{1} ∪K_{1} as components then it doesn’t have a TMI. However K_{1} as a component is allowed, we have:

Theorem 2.3 Let G not have an isolate. Then K_{1} ∪ G has a TMI if and only if G has a TMI.

Proof. If K_{1} ∪ G has a TMI then, from Theorem 2.2, so does G.

For the backward implication: Let μ, with constants h and k, denote the TMI of G, let us say that it is a [m]-TMI of G. Now G does not have an isolate so, from Lemma 2.1, h > m. Hence h has not been used as a label in G.

Let z be the isolate in K_{1} ∪ G. Now define an injection μ_{ext} of K_{1} ∪ G as follows: μ_{ext}(z) = h, and μ_{ext}(x) = μ(x) for every vertex x ∈ V (G) and μ_{ext}(xy) = μ(xy) for every edge xy ∈ E(G). It is straightforward to check that μ_{ext} is a TMI of K_{1} ∪ G.

Corollary 2.4 Let G have a TMI μ and not have an isolate. Then μ can be extended to a TMI of K_{1} ∪ G, with the same vertex and edge constants.

Proof. The TMI of K_{1} ∪G μ_{ext} defined above in the proof of Theorem 2.3 has the same constants as μ.

Remark We will always use the notation μ_{ext} for the extension of μ from G to K_{1} ∪ G as indicated in Corollary 2.4.

Example 2 The extension of a [6]-TMI of K_{3} with h = 9 and k = 12 to a [9]-TMI of K_{1} ∪ K_{3} with h = 9 and k = 12.

[figure: 5; 4; 6; 1; 2; 3; K_{3}; →; 5; 4; 6; 1; 2; 3; K_{1} ∪ K_{3}; 9]

Recalling that K_{2} doesn’t have a TMI, a necessary condition for G to have a TMI is given below:

Theorem 2.5 Let G have a TMI. Then either

(i) G has exactly one isolate and all remaining components have ≥ 3 vertices and have a TMI, or

(ii) all components of G have ≥ 3 vertices and have a TMI.

3 Star Theorem, Connected G without a TMI, Forbidden Configurations

The following Theorem has proved useful in eliminating graphs that may have a TMI. Many results produced from it appear in [2], namely Theorems 3.3, 3.5, 3.7, 3.9, and 3.11, and Corollaries 3.4, and 3.6. Thus many of the Theorems in [2] which were used to exclude the possibility of TMLs actually exclude the possibility of TMIs. We call this Theorem the ‘Star Theorem’. We note that the Star Theorem could have been used to prove many of the results in [2]. We only consider connected graphs in this section.

Let G have a TMI μ with vertex and edge constants h and k. Let a be any vertex in G with neighbors {x_{1}, x_{2}, …, x_{d}}. For every i = 1, 2, …, d let X_{i} = ∑_{y≠a^{y∼x_{i}}} μ(x_{i}y), i.e., let X_{i} be the sum of the labels of all edges incident to x_{i} and ‘outside’ the star centered at a.

[figure: .; .; .; a; x_{1}; x_{2}; x_{3}; x_{d−1}; x_{d}; X_{1}; X_{2}; X_{3}; X_{d−1}; X_{d}]

Theorem 3.1 (Star Theorem) With the above G, μ, and a we have

X_{1} = X_{2} = ⋯ = X_{d} = h − k + μ(a),

which is constant for a fixed vertex a.

Proof. For every i = 1, 2, …, d we have

h = wt(x_{i}) = μ(x_{i}) + μ(x_{i}a) + X_{i},
k = wt(x_{i}a) = μ(x_{i}) + μ(x_{i}a) + μ(a),

so X_{i} = h − k + μ(a), which is constant for a fixed vertex a.

The next result is due to Brown [1].

Corollary 3.2 Let G have a TMI μ. Let α be any edge in G then

μ(α) + ∑_{β∼α} μ(β) = 2h − k,

a constant, where the sum is over all edges β adjacent to α.

Proof. Here α = ab.

[figure: a; A; b; B]

Let A be the sum of the labels of all edges incident to a and outside the star centered at b, define B similarly. From above A = h − k + μ(b) and B = h − k + μ(a). So μ(α) + ∑_{β∼α} μ(β) = μ(α) + A + B = 2h − k.

The next five Theorems are all proved using the Star Theorem, after each Theorem we give a simple Corollary.

Theorem 3.3 Let G have a TMI. If G has a vertex of degree 1 then the component of G containing it is a star.

Proof. Let x_{1} have degree 1 and let x_{1} be adjacent to a. Let a also be adjacent to the vertices {x_{2}, …, x_{d}}. Applying the Star Theorem at a yields X_{1} = X_{2} = ⋯ = X_{d}. But X_{1} = 0 because x_{1} has degree 1, so X_{2} = ⋯ = X_{d} = 0 also, and a is the center of a star.

Corollary 3.4

(i) Every connected graph with a vertex of degree 1 that is not a star does not have a TMI.

(ii) Every tree that is not a star does not have a TMI.

In the next section we will see that for every n ≥ 2 the star K_{1,n} does in fact have a TMI.

Theorem 3.5 Let G have a TMI. If G has two adjacent vertices of degree 2 then the component of G containing them is a triangle.

Proof. Let the TMI of G be μ, and let the two adjacent vertices of degree 2 be a and b and let a ∼ x and b ∼ y, see (i) below:

[figure: a; b; x; X; y; Y; (i); a; b; C − μ(bc); c; C; (ii)]

Applying the Star Theorem at a gives X = μ(by) and at b gives Y = μ(ax). Now wt(x) = wt(y) gives μ(x) + μ(ax) + X = μ(y) + μ(by) + Y, hence μ(x) = μ(y), and, because μ is an injection, we have x = y. So we have (ii) above, where we denote vertex x = y by c. Now applying the Star Theorem at a again gives C = μ(bc), so C − μ(bc) = 0. But C − μ(bc) is the sum of the edge labels of all edges incident to c and outside triangle abc, thus abc is a triangle component.

For n ≥ 1 let P_{n} denote the path on n vertices, and for n ≥ 3 let C_{n} denote the cycle on n vertices.

Corollary 3.6 For every n ≥ 4 the path P_{n} and the cycle C_{n} does not have a TMI.

Theorem 3.7 Suppose that G contains two vertices with a common neighbor. If these two vertices each have degree 2, or are adjacent and each have degree 3, then G does not have a TMI.

Proof. Let the two vertices be a and b with common neighbor x. For the case in which deg(a) = deg(b) = 2 let a ∼ a_{1} and b ∼ b_{1}.

[figure: a; b; a_{1}; b_{1}; x]

Suppose that G has a TMI μ. Applying the Star Theorem at x gives μ(aa_{1}) = μ(bb_{1}), a contradiction. Similarly if deg(a) = deg(b) = 3 and a ∼ b.

For n ≥ 3 let W_{n} denote the wheel with one vertex in the center and n vertices on the rim, and let F_{n} denote the fan obtained from W_{n} by removing one rim edge. By using Theorem 3.7 with a and b as rim vertices and x as the center we have:

Corollary 3.8 For every n ≥ 3 the wheel W_{n} and the fan F_{n} does not have a TMI.

Theorem 3.9 Let G have a TMI, and let G contain a triangle. Then the sum of the labels of all edges outside the triangle and incident with any one vertex of the triangle is the same, whichever vertex of the triangle is chosen.

Proof. Let the TMI of G be μ, and let the three vertices of a triangle be a, b, and c. Let A be the sum of the labels of all edges incident to a and outside the triangle, i.e., except for edges ab and ac; define B and C similarly.

[figure: A; a; b; B; c; C]

Applying the Star Theorem at a gives B + μ(bc) = C + μ(bc), so B = C; similarly applying it at b gives A = C. Hence A = B = C.

Corollary 3.10 Any graph that contains a triangle with exactly one or exactly two vertices of degree 2 does not have a TMI.

Theorem 3.11 Let G have two vertices that are each adjacent to exactly the same set of other vertices of size ≥ 2. Then G does not have a TMI. (The two vertices themselves may be adjacent or non-adjacent.)

Proof. Consider the case when the two vertices a and b are non-adjacent, let them both be adjacent to {x_{1}, x_{2}, …, x_{d}} where d ≥ 2, and to no other vertices.

[figure: a; b; X_{1}; x_{1}; X_{2}; x_{2}; X_{d}; x_{d}]

For i = 1, 2, …, d let X_{i} be the sum of the labels of all edges incident to x_{i} and outside the neighborhood graph shown above, i.e., except edges x_{i}a and x_{i}b. Applying the Star Theorem to a gives X_{i} +μ(x_{i}b) = h−k +μ(a), and to b gives X_{i} + μ(x_{i}a) = h − k + μ(b). So μ(x_{i}a) − μ(x_{i}b) = μ(b) − μ(a) ≠ 0 for every i. Now wt(a) = wt(b), i.e., μ(a) + ∑_{i=1}^{d} μ(x_{i}a) = μ(b) + ∑_{i=1}^{d} μ(x_{i}b). So ∑_{i=1}^{d}(μ(x_{i}a) − μ(x_{i}b)) = μ(b) − μ(a), i.e., d (μ(b) − μ(a)) = μ(b) − μ(a), a contradiction because d ≥ 2. The proof is similar if a ∼ b.

For n ≥ 1 let K_{n} denote the complete graph with n vertices, and for p ≥ 2 let K_{n_{1},n_{2},...,n_{p}} denote the complete p-partite graph with n_{j} ≥ 1 vertices in part j for every j = 1, 2, …, p.

Corollary 3.12

(i) For every n ≥ 4 the complete graph K_{n} does not have a TMI.

(ii) p = 2. For every pair {n_{1}, n_{2}} with both n_{1} ≥ 2 and n_{2} ≥ 2 the complete bipartite graph K_{n_{1},n_{2}} does not have a TMI.

(iii) p ≥ 3. For every p-set {n_{1}, n_{2}, …, n_{p}} with at least one n_{j} ≥ 2 the complete p-partite graph K_{n_{1},n_{2},...,n_{p}} does not have a TMI.

If a graph G has one of the configurations mentioned in Theorems 3.3, 3.5, 3.7, 3.9, or 3.11 then it does not have a TMI. Thus the configurations given in these Theorems are ‘forbidden configurations’, they forbid G from having a TMI. Below we have shown all forbidden configurations which come from these Theorems. Here a number i next to a vertex indicates a vertex of degree exactly i, and the two short lines attached to a vertex indicate that there may or may not be further edges incident to it.

Forbidden Configurations

If a graph contains any of these configurations then it does not have a TMI.

[figure: 1; 2; 2; 2; 2]

[figure: 2; 2; 3; 3; 2]

[figure: d; d; d ≥ 2; d + 1; d + 1; d ≥ 2]

4 Forests

Here we determine m_{t}(F) and def_{t}(F) for every forest F that has a TMI.

First consider the star F = K_{1,n} for n ≥ 2. From Corollary 3.2 of [2] the only star with a TML is K_{1,2}, hence m_{t}(K_{1,2}) = 5.

Theorem 4.1 For n ≥ 3 we have m_{t}(K_{1,n}) = \binom{n + 2}{2} − 2.

Proof. Let the center of K_{1,n} be c, let the outer vertices be {x_{1}, x_{2}, …, x_{n}}, and let K_{1,n} have TMI μ. Without loss of generality let the n edge labels satisfy:

1 ≤ μ(cx_{1}) < μ(cx_{2}) < ⋯ < μ(cx_{n}).  (1)

For any fixed j = 1, 2, …, n we have wt(c) = wt(x_{j}), so

μ(c) + ∑_{i=1}^{n} μ(cx_{i}) = μ(x_{j}) + μ(cx_{j}),

and so

μ(x_{j}) = μ(c) + ∑_{i≠j^{i=1}}^{n} μ(cx_{i}).  (2)

Now, from (1) and (2), for j = 1, 2, …, n clearly μ(x_{j}) is largest when j = 1. That is, μ(x_{1}) > μ(x_{j}) for every j = 2, …, n. Also from (2) we have μ(x_{1}) > μ(c), hence μ(x_{1}) is the largest vertex label. But again from (2) we have μ(x_{1}) > μ(cx_{n}), so, from (1) again, μ(x_{1}) is larger than every edge label. Thus μ(x_{1}) = m is the largest label.

Now we minimize m = μ(x_{1}) = μ(c) + ∑_{i=2}^{n} μ(cx_{i}). We first determine where to place the label 1.

From (1), for each i = 2, …, n, we have μ(cx_{i}) ≥ 2 , i.e., 1 is not an edge label for any edge cx_{i} for i = 2, …, n. Hence, to minimize m, we first let μ(c) = 1. Now if μ(cx_{2}) = 2 then μ(cx_{1}) = 1, a contradiction. So we finish the minimization of m by letting μ(cx_{2}) = 3, μ(cx_{3}) = 4, …, i.e., by letting μ(cx_{i}) = i + 1 for each i = 2, …, n. Hence the minimum m is m = 1 + 3 + ⋯ + (n + 1) = \binom{n+2}{2} − 2.

We now let μ(cx_{1}) = 2 and μ(x_{i}) = \binom{n+2}{2} − (i + 1) for each i = 2, …, n, so all vertices and edges have been labeled.

The labels \{1, 2, …, n+1, \binom{n+2}{2}−(n + 1), \binom{n+2}{2}−n, …, \binom{n+2}{2}−2\} are all distinct provided that \binom{n+2}{2} − (n + 1) > n + 1, i.e., provided that n ≥ 3. It is straightforward to check that this labeling is a TMI of K_{1,n}, (with h = \binom{n+2}{2} and k = \binom{n+2}{2} + 1), and is therefore a minimal TMI.

Corollary 4.2 For n ≥ 3 we have m_{t}(K_{1} ∪ K_{1,n}) = \binom{n + 2}{2}.

Proof. The above minimal TMI μ of K_{1,n} has h = \binom{n+2}{2}. Now apply Corollary 2.4 with G = K_{1,n} to obtain the TMI μ_{ext} of K_{1} ∪ K_{1,n} with m_{μ_{ext}} = \binom{n+2}{2}.

Now let μ_{1} be an arbitrary TMI of K_{1} ∪ K_{1,n}. Then, from Lemma 2.1(ii), since K_{1} ∪ K_{1,n} has an isolate, we have m_{μ_{1}} = h_{μ_{1}}. Let c denote the center of K_{1,n} then h_{μ_{1}} = wt_{μ_{1}}(c) ≥ ∑_{i=1}^{n+1} = \binom{n+2}{2}. So m_{μ_{1}} ≥ \binom{n+2}{2}, and hence μ_{ext} above is a minimal TMI of K_{1} ∪ K_{1,n}.

Theorem 4.3 The only forests F that have a TMI are K_{1}, or K_{1,n} for n ≥ 2, or K_{1} ∪ K_{1,n} for n ≥ 2. Furthermore we have (n ≥ 3):

m_{t}(F) = \begin{cases}1, 5, 6 & if F = K_{1}, K_{1,2}, K_{1} ∪ K_{1,2}, \\ \binom{n + 2}{2} − 2 & if F = K_{1,n}, \\ \binom{n + 2}{2} & if F = K_{1} ∪ K_{1,n}. \end{cases}

Proof. Let the forest F have a TMI. Every component of F has a vertex of degree 1, and so, from Theorem 3.3, every component of F is a star, and F is a union of stars. Hence, from Theorem 2.5, either (i) F = K_{1}∪K_{1,n_{1}}∪K_{1,n_{2}}∪⋯ where each n_{i} ≥ 2, or (ii) F = K_{1,n_{1}} ∪ K_{1,n_{2}} ∪ ⋯ where each n_{i} ≥ 2.

Now suppose that F contains at least two stars K_{1,n_{i}}, where each n_{i} ≥ 2. Then it is straightforward to show that the labels on the centers of each of these stars is k −h, a contradiction. Hence F contains at most one star K_{1,n}, where n ≥ 2.

Hence either (i) F = K_{1} or F = K_{1} ∪ K_{1,n} for n ≥ 2, or (ii) F = K_{1,n} for n ≥ 2. Now the three forests K_{1}, K_{1,2}, and K_{1} ∪ K_{1,2} each have a TML. Hence m_{t}(K_{1}) = 1, m_{t}(K_{1,2}) = 5, and m_{t}(K_{1} ∪ K_{1,2}) = 6. This fact and the previous two results complete the proof.

Finally, using def_{t}(F) = m_{t}(F) − v − e, we have:

Theorem 4.4 Let F be a forest that has a TMI. Then the total deficiency of F is given by (n ≥ 3):

def_{t}(F) = \begin{cases}0, 0, 0 & if F = K_{1}, K_{1,2}, K_{1} ∪ K_{1,2}, \\ \frac{n^{2} − n − 4}{2} & if F = K_{1,n}, \\ \frac{n^{2} − n − 2}{2} & if F = K_{1} ∪ K_{1,n}. \end{cases}

Example 3 The minimal [\binom{n+2}{2}−2]-TMI of K_{1,n} together with the n = 3 case, giving a minimal [8]-TMI of K_{1,3}, is shown first below. Then the minimal [\binom{n+2}{2}]-TMI of K_{1} ∪ K_{1,n} together with the n = 3 case, giving a minimal [10]-TMI of K_{1} ∪ K_{1,3}, is shown.

[figure: .; .; .; c; 1; x_{1}; x_{2}; x_{3}; x_{n−1}; x_{n}; ^{\binom{n+2}{2}}−2; 2; ^{\binom{n+2}{2}}−3; 3; ^{\binom{n+2}{2}}−4; 4; ^{\binom{n+2}{2}}−n; n; ^{\binom{n+2}{2}}−(n+1); n+1; K_{1,n}; 1; 8; 6; 7; 2; 4; 3; K_{1,3}]

[figure: .; .; .; c; 1; x_{1}; x_{2}; x_{3}; x_{n−1}; x_{n}; ^{\binom{n+2}{2}}−2; 2; ^{\binom{n+2}{2}}−3; 3; _{\binom{n+2}{2}}−4; 4; _{\binom{n+2}{2}}−n; n; ^{\binom{n+2}{2}}−(n+1); n+1; K_{1} ∪ K_{1,n}; ^{\binom{n+2}{2}}; 1; 8; 6; 7; 2; 4; 3; 10; K_{1} ∪ K_{1,3}]

5 TMI-Survivor, Graphs with ≤ 6 vertices that have a TMI

In this section we define a TMI-survivor. Then we find all graphs G with ≤ 6 vertices that have a TMI, and, for each of them, the numbers m_{t}(G) and def_{t}(G).

Because of Theorem 2.2 when searching for graphs with a TMI we start searching amongst connected graphs.

Borrowing the idea of a survivor from §6 of [2] we define a TMI-survivor to be a simple graph (≠ K_{2}) that is connected and that does not contain any of the forbidden configurations given at the end of §3. (Note that a TMI-survivor need not have a TMI, however the smallest that does not have a TMI has 7 vertices.)

A list of the 143 connected graphs with ≤ 6 vertices is given on pp.7–9 of Steinbach [4]. Of these there are exactly six TMI-survivors: K_{1}, K_{1,2}, K_{3}, K_{1,3}, K_{1,4}, and K_{1,5}, and all six have a TMI.

We then used these TMI-survivors as components to find a further six disconnected graphs that have a TMI: K_{1}∪K_{1,2}, K_{1}∪K_{3}, K_{1}∪K_{1,3}, K_{1}∪K_{1,4}, K_{1,2} ∪ K_{3}, and K_{3} ∪ K_{3}.

Thus, in total, there are exactly 12 graphs with ≤ 6 vertices that have a TMI. Of these 12 graphs eight are forests and have been considered in Theorems 4.3 and 4.4. The remaining four graphs G, and their numbers m_{t}(G) and def_{t}(G), are given in the Table below.

G  m_{t}(G) def_{t}(G)  Comments
K_{3}  6  0  Example 1(iii)
K_{1} ∪ K_{3}  9  2  See Remark 1 below
K_{1,2} ∪ K_{3} 13  2  See Remark 3 below
K_{3} ∪ K_{3}  14  2  See Remark 2 below

Remarks

1. K_{1} ∪ K_{3}.

Example 2 gives a [9]-TMI of K_{1} ∪ K_{3}. From Theorem 4 of [2] we know that K_{1} ∪ K_{3} doesn’t have a TML, i.e., doesn’t have a [7]-TMI. Let z denote the K_{1} component in K_{1} ∪K_{3}. From Lemma 2.1(ii) if {z}∪K_{3} has a [8]-TMI then h = m = μ(z) = 8. So the remaining six labels for the K_{3} component must come from the set {1, 2, 3, 4, 5, 6, 7}. But clearly using 6 or 7 as a label on the K_{3} component with h = 8 gives a contradiction. Hence K_{1} ∪ K_{3} doesn’t have a [8]-TMI. So m_{t}(K_{1} ∪ K_{3}) = 9 and def_{t}(K_{1} ∪ K_{3}) = 2.

2. K_{3} ∪ K_{3}.

We have proved the following Theorem in [3]:

Theorem 5.1 Let s ≥ 2 be even.

Then m_{t}(sK_{3}) = 6s + 2 and def_{t}(sK_{3}) = 2.

A minimal [14]-TMI of K_{3} ∪ K_{3} (with h = 19 and k = 26) is:

[figure: 8; 13; 12; 6; 1; 5; 9; 14; 10; 7; 2; 3]

3. K_{1,2} ∪ K_{3}.

Consider the above [14]-TMI of K_{3} ∪ K_{3}. Subtract 1 from each label, and remove the edge with label 0. This gives the [13]-TMI of K_{1,2} ∪ K_{3} (with h = 16 and k = 23) below.

[figure: 7; 12; 11; 4; 5; 8; 13; 9; 6; 1; 2]

To show that this is a minimal TMI we must show that K_{1,2} ∪ K_{3} doesn’t have an [11]- or [12]-TMI:

Consider the ‘generic’ labeling of K_{1,2} = {x, y, z} under TMI μ with constants h and k below:

[figure: k − h; h − ℓ_{2}; h − ℓ_{1}; ℓ_{2}; ℓ_{1}; x; y; z]

That is: μ(x) = h − ℓ_{1}, μ(y) = k − h, μ(z) = h − ℓ_{2}, μ(xy) = ℓ_{1}, and μ(yz) = ℓ_{2}. Now, from Corollary 3.2, we have ℓ_{1} + ℓ_{2} = 2h − k. So μ(x) + μ(z) = k. Thus if we include edge xz with μ(xz) = 0, then wt(xz) = k. Then we can add 1 to all labels to arrive at a TMI of K_{3}. Clearly if there was an [11]- or [12]-TMI of K_{1,2} ∪ K_{3} then applying the above process to the K_{1,2} component (and adding 1 to each label in the K_{3} component) would produce a [12]- or [13]-TMI of K_{3} ∪ K_{3}, a contradiction from Remark 2. Hence the above [13]-TMI of K_{1,2} ∪ K_{3} is a minimal TMI. We have m_{t}(K_{1,2} ∪ K_{3}) = 13 and def_{t}(K_{1,2} ∪ K_{3}) = 2.

A summary of the situation for vertex-magic injections/edge-magic injections/TMIs for graphs with ≤ 6 vertices is given below:

(i) amongst the 143 connected graphs with ≤ 6 vertices exactly 142 (all except K_{2}) have a vertex-magic injection, all 143 have an edge-magic injection, but only 6 have a TMI, (ii) amongst the 208 graphs with ≤ 6 vertices exactly 174 have a vertexmagic injection, all 208 have an edge-magic injection, but only 12 have a TMI.

References

[1] D.Brown. Personal communication, (2001).

[2] G.Exoo, A.C.H.Ling, J.P.McSorley, N.C.K.Phillips, W.D.Wallis. Totally Magic Graphs, Discrete Mathematics, 254, 103–113, (2002).

[3] J.P.McSorley, Solutions of some Research Problems in Totally Magic Labelings and Totally Magic Injections of Graphs, in preparation.

[4] P.Steinbach. Field guide to Simple Graphs, 1, Design Lab, Albuquerque, (1999).

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