Totally Magic Graphs

Geoffrey Exoo

Department of Mathematics and Computer Science, Indiana State University,

          Terre Haute, IN, USA 47809 ge@ginger.indstate.edu

Alan C.H. Ling

Department of Mathematical Sciences, Michigan Technological University, Houghton, MI, USA 49931 aling@mtu.edu

John P. McSorley

Department of Mathematics, Southern Illinois University, Carbondale IL, USA 62901-4408 jmcsorley@math.siu.edu

N. C. K. Phillips

Department of Computer Science, Southern Illinois University, Carbondale IL, USA 62901-4511 nckp@siu.edu

W. D. Wallis

Department of Mathematics, Southern Illinois University, Carbondale IL, USA 62901-4408 wdwallis@math.siu.edu

Abstract

A total labeling of a graph with v vertices and e edges is defined as a one-to-one map taking the vertices and edges onto the integers 1, 2, ⋯, v+e. Such a labeling is vertex magic if the sum of the label on a vertex and the labels on its incident edges is a constant independent of the choice of vertex, and edge magic if the sum of an edge label and the labels of the endpoints of the edge is constant. In this paper we examine graphs possessing a labeling that is simultaneously vertex magic and edge magic. Such graphs appear to be rare.

Preprint submitted to Elsevier Preprint 23 July 2006

1 Introduction

All graphs in this paper are finite, simple and undirected. Unless otherwise specified, the graph G has vertex set V = V (G) and edge set E = E(G) and we write e for |E| and v for |V |. A general reference for graph theoretic notions is [6].

A labeling for a graph is a map that takes graph elements to numbers (usually positive or non-negative integers). In this paper the domain is the set of all vertices and edges; such labelings are called total. Other domains have also been studied. The most complete recent survey of graph labelings is [2].

In many cases, it is interesting to consider the sum of all labels associated with a graph label. This will be called the weight of the element. For example, the weight of vertex x under the total labeling λ is

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

while

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

If necessary, the labeling can be specified by a subscript, as in wt_{λ}(x).

Various authors have introduced labelings that generalize the idea of a magic square, by requiring that certain weights be constant. Kotzig and Rosa [3], for example, defined a magic labeling to be a labeling on the vertices and edges in which the labels are the integers from 1 to v + e and where the sum of labels on an edge and its two endpoints is constant. Related labelings have been studied by other authors and there are numerous variations in the terminology used. Readers are referred to [1] for a discussion of these matters and a standardization of the terminology.

In particular, we treat two types of total labeling. For detailed treatment of the two types taken separately, see [1] and [4].

An edge magic total labeling or EMTL on G is a one-to-one map λ from V (G) ∪ E(G) onto the integers 1, 2, …, v + e, with the property that, given any edge xy,

λ(x) + λ(xy) + λ(y) = k

for some constant k. In other words, wt(xy) = k for any edge xy.

A vertex magic total labeling or VMTL on G is a one-to-one map λ from V (G) ∪ E(G) onto the integers 1, 2, …, v + e, with the property that, given any vertex x,

λ(x) + ∑_{y∼x} λ(xy) = h

for some constant h, where the sum is over all vertices y adjacent to x. In this case the magic requirement is wt(x) = h for all vertices x.

Suppose λ is a vertex magic total labeling of G. Then the sum of all vertex weights is

hv = ∑_{x∈V} λ(x) + 2 ∑_{y∈E} λ(y)
= (1 + 2 + … + (v + e)) + ∑_{y∈E} λ(y)
= \frac{1}{2}(v + e)(v + e + 1) + ∑_{y∈E} λ(y).  (1)

Similarly, if μ is an edge magic total labeling, then the sum of all edge weights is

ke = ∑_{x∈V} d_{x}μ(x) + ∑_{y∈E} μ(y)
= \frac{1}{2}(v + e)(v + e + 1) + ∑_{x∈V} (d_{x} − 1)μ(x),  (2)

where d_{x} is the degree of x. As

1 + 2 + … + e ≤ ∑_{y∈E} λ(y) ≤ (v + 1) + (v + 2) + … + (v + e),

(1) can be used to find upper and lower bounds for h. A similar approach, taking the degree sequence into account, yields upper and lower bounds for k.

In this paper we investigate the question: for a graph G does there exist a total labeling λ that is both edge magic and vertex magic? We shall call such a λ a totally magic labeling and call G a totally magic graph. The constants h and k will be called the vertex constant and edge constant respectively. We do not require that h = k.

2 Examples

One quickly constructs three small examples of connected totally magic graphs; see below.

[figure: K_{1}; C_{3}; P_{3}; K_{1} ∪ P_{3}]

An obvious trivial example is the single vertex graph K_{1}. There are four totally magic labelings of the triangle K_{3}; if the set of vertex-labels is denoted by S_{v}, then the labelings have

\begin{aligned}h & = & 9, & k & = & 12, & S_{v} & = & \{4, 5, 6\} \\ h & = & 10, & k & = & 11, & S_{v} & = & \{2, 4, 6\} \\ h & = & 11, & k & = & 10, & S_{v} & = & \{1, 3, 5\} \\ h & = & 12, & k & = & 9, & S_{v} & = & \{1, 2, 3\}. \end{aligned}

(There is an obvious duality here.) The three-vertex path P_{3} has two labelings. Writing the labels in sequence vertex-edge-vertex-edge-vertex, they are

h = 6, k = 9, labels 4, 2, 3, 1, 5,
h = 7, k = 8, labels 3, 4, 1, 2, 5.

Among disconnected graphs, we know that there is exactly one totally magic labeling of K_{1} ∪ P_{3}, constructed from the first of the P_{3}-labelings listed above by mapping the isolated vertex to 6.

3 Isolates and stars

If λ is a totally magic labeling of G with vertex constant h then any isolated vertex x has λ(x) = h, so there cannot be two such vertices. Similarly, an isolated edge would have equal labels on its endpoints. We have:

Lemma 1 No totally magic graph has two isolated vertices or an isolated edge.

Moreover, if K_{1} ∪ G is totally magic, the isolated vertex must necessarily receive the largest possible label, so the remaining labels form a totally magic labeling of G. We have:

Lemma 2 If a graph with an isolated vertex is totally magic, then the graph G resulting from the deletion of the isolate has a totally magic labeling with vertex sum |V (G)| + |E(G)| + 1.

The labeling of K_{1} ∪ P_{3} given above is as described in this lemma.

A vertex of degree 1 is often called a leaf.

Theorem 3 Suppose the totally magic graph G has a leaf x. Then the component of G containing x is a star.

Proof. Suppose λ is a totally magic labeling on G, with vertex and edge constants h and k respectively, and suppose x is a leaf with neighbor y. By the vertex magic property, λ(x) + λ(xy) = h, and by the edge magic property, λ(x) + λ(xy) + λ(y) = k. So λ(y) = k − h.

By Lemma 1, y has a neighbor, z say. Then k = λ(y) + λ(yz) + λ(z) = λ(yz) + λ(z) + k − h, so λ(yz) = h − λ(z). So wt(z) ≥ λ(z) + λ(yz) = h, with equality only if z has degree 1. So every vertex adjacent to y has degree 1, and the component of G containing y is a star with center y. □

Corollary 3.1 The only connected totally magic graph containing a vertex of degree 1 is P_{3}.

Every non-trivial tree has at least two vertices of degree 1, so the only possible magic trees are K_{1} and the stars. But it was shown in Theorem 5 of [4] that K_{m,n} is never vertex magic when |m − n| > 1. So no star larger than K_{1,2} is vertex magic, so

Corollary 3.2 The only totally magic trees are K_{1} and P_{3}.

A totally magic graph cannot have two stars as components, because their centers would each receive label k − h. It follows that the components of a totally magic graph can include at most one K_{1} and at most one star, and all other components have minimum degree at least 2, and consequently have as many edges as vertices.

Corollary 3.3 The only totally magic proper forest is K_{1} ∪ P_{3}.

Theorem 4 The only totally magic graphs with a component K_{1} are K_{1} ∪ P_{3} and K_{1} itself.

Proof. Suppose K_{1} ∪ G is a totally magic graph; K_{1} has vertex x, and G has v vertices and e edges, as usual. G may have a star as a component, but any other component has minimum degree at least 2, so e ≥ v − 1. From Lemma 2,

h = λ(x) = v + e + 1,

and G is totally magic with vertex constant h. Now from (1),

v(v + e + 1) = \frac{1}{2}(v + e)(v + e + 1) + ∑_{y∈E} λ(y).

So

∑_{y∈E} λ(y) = \frac{1}{2}(v − e)(v + e + 1).

But ∑ λ(y) ≥ \frac{1}{2}e(e + 1), so

e(e + 1) ≤ (v − e)(v + e + 1),

and

2e(e + 1) ≤ v(v + 1).

Clearly e < v. So e = v − 1, whence

2(v^{2} − v) ≤ v^{2} + v,

and v ≤ 3. The only possibility is G = P_{3}. □

4 Forbidden configurations

Theorem 5 If a totally magic graph G contains two adjacent vertices of degree 2, then the component containing them is a cycle of length 3.

Proof. Suppose G contains a pair of adjacent vertices b and c, each having degree 2, and suppose λ is a totally magic labeling of G with vertex and edge constants h and k.

First, assume G contains a path {a, b, c, d}, where a and d are distinct vertices. From h = wt(b) = wt(c) it follows that

λ(ab) + λ(b) + λ(bc) = λ(bc) + λ(c) + λ(cd),

from which

λ(cd) = λ(ab) + λ(b) − λ(c)  (3)

while the edge magic property yields

k = λ(a) + λ(ab) + λ(b) = λ(b) + λ(bc) + λ(c) = λ(c) + λ(cd) + λ(d); (4)

the second equality in (4) implies

λ(cd) = λ(b) + λ(bc) − λ(d)  (5)

while the first gives

λ(a) + λ(ab) = λ(bc) + λ(c).  (6)

But (3) and (5) give

λ(ab) − λ(c) = λ(bc) − λ(d)

so

λ(d) = λ(bc) + λ(c) − λ(ab)  (7)

and (6) and (7) together imply λ(a) = λ(d), a contradiction. Now assume b and c have a common neighbor, a say, and suppose a has some other neighbor, z. ¿From (4) we see

λ(ab) = k − λ(a) − λ(b),

and similarly for bc and ca, so

wt(b) = λ(ab) + λ(b) + λ(bc)
= 2k − λ(a) − λ(b) − λ(c),

whereas

wt(a) = λ(ca) + λ(a) + λ(ab) + λ(az) + …
≥ 2k − λ(a) − λ(b) − λ(c) + λ(az)
> wt(a),

as λ(az) > 0. □ Corollary 5.1 No totally magic graph contains as a component a path other than P_{3} or a cycle other than K_{3}. (Lemma 1 must be invoked to rule out P_{2}.) In particular, Corollary 5.2 The only totally magic cycle is K_{3}. Theorem 6 Suppose G contains two vertices, x_{1} and x_{2}, that are each adjacent to precisely the same set {y_{1}, y_{2}, …, y_{d}} of other vertices. (It is not specified whether x_{1} and x_{2} are adjacent.) If d > 1 then G is not totally magic.

Proof. Suppose λ is a totally magic labeling of G with vertex and edge sums h and k. For convenience, define λ(x_{1}x_{2}) = 0 if x_{1} is not adjacent to x_{2}. Then

h = λ(x_{i}) + ∑_{j=1}^{d} λ(x_{i}y_{j}) + λ(x_{1}x_{2}), i = 1, 2,

and

k = λ(x_{i}) + λ(x_{i}y_{j}) + λ(y_{j}), i = 1, 2, 1 ≤ j ≤ d.

So

dk = dλ(x_{i}) + ∑_{j=1}^{d} λ(x_{i}y_{j}) + ∑_{j=1}^{d} λ(y_{j}), i = 1, 2,

= (d − 1)λ(x_{i}) + (h − λ(x_{1}x_{2})) + ∑_{j=1}^{d} λ(y_{j}), i = 1, 2,

so

(d − 1)λ(x_{1}) = (d − 1)λ(x_{2}),

a contradiction unless d = 1. □

Corollary 6.1 The only totally magic complete graphs are K_{1} and K_{3}. The only totally magic complete bipartite graph is K_{1,2}.

Theorem 7 Suppose G contains two vertices, x and y, with a common neighbor. If x and y are nonadjacent and each has degree 2, or are adjacent and each has degree 3, then G is not totally magic.

Proof. Denote the common neighbor by z, the other neighbor of x by x_{1}, and the other neighbor of y by y_{1}. (Possibly x_{1} = y_{1}.) Suppose λ is a totally magic labeling of G with vertex and edge constants h and k; if x is not adjacent to y in G then define λ(xy) = 0.

The weight of x is

wt(x) = λ(x) + λ(xx_{1}) + λ(xz) + λ(xy)
= λ(x) + (k − λ(x) − λ(x_{1})) + (k − λ(x) − λ(z)) + λ(xy)
= 2k − (λ(x) + λ(x_{1}) + λ(z)) + λ(xy)

and similarly

wt(y) = 2k − (λ(y) + λ(y_{1}) + λ(z)) + λ(xy).

From the vertex magic property, wt(x) = wt(y), so λ(x)+λ(x_{1}) = λ(y)+λ(y_{1}). So λ(xx_{1}) = k −λ(x)−λ(x_{1}) = k −λ(y)−λ(y_{1}) = λ(yy_{1}). But this contradicts the edge magic property. □

(The case where x and y are adjacent could be rephrased, a totally magic graph G cannot contain a triangle with two vertices of degree 3.)

Theorem 8 Suppose the totally magic graph G contains 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 is chosen.

Proof. Suppose the triangle is xyz. Write X for the sum of the labels of all edges other than xy and xz that are adjacent to x; define Y and Z similarly. Then

h = wt(x) = λ(x) + λ(xy) + λ(xz) + X = 2k − λ(x) − λ(y) − λ(z) + X

= wt(y) = λ(y) + λ(xy) + λ(yz) + Y = 2k − λ(x) − λ(y) − λ(z) + Y = wt(z) = λ(z) + λ(xz) + λ(yz) + Z = 2k − λ(x) − λ(y) − λ(z) + Z

so X = Y = Z. □

Corollary 8.1 If the totally magic graph G contains a triangle with one vertex of degree 2, then the triangle is a component of G.

Observe that Theorems 5, 6, 7 and 8 are essentially forbidden configuration theorems. If a graph G is in violation of one of them, then not only is G not totally magic, but G cannot be a component or union of components in any totally magic graph. We term a graph a survivor if it is not eliminated by the application of these theorems.

5 Unions of triangles

In this section we construct two infinite families of totally magic graphs, both based on triangles. We use the following Lemma, which has been proved several times in the literature.

Lemma 9 The set of integers {1, 2, ⋯, 3n} can be partitioned into n triples, where the sum of elements in any triple is \frac{3}{2}(3n + 1), if and only if n is odd.

Proof. Observe that 1 + 2 + … + 3n = 3n(3n + 1)/2, so the only possible common sum is \frac{3}{2}(3n + 1).

First suppose n is odd. For i = 1, 2, …, n, take x_{i} to be the integer such that x_{i} = 3n − 2i + 2 and 2n + 1 ≤ x_{i} ≤ 3n, and take y_{i} to be the integer such that y_{i} = (3n+2i−1)/2 and n+1 ≤ y_{i} ≤ 2n. Then one solution is {S_{1}, S_{2}, …, S_{n}}, where S_{i} = {i, x_{i}, y_{i}}.

If n is even, then \frac{3}{2}(3n + 1) is not an integer. □

Theorem 10 There is a totally magic labeling of nK_{3}, the disjoint union of n triangles, whenever n is odd.

Proof. Choose n 3-sets as defined in Lemma 9. For each triangle, label the edges with the members of the triple. If edge xy receives label λ(xy), the vertex opposite xy receives 3n + λ(xy). As the three edge-labels on a triangle sum to \frac{3}{2}(3n + 1), the edges all have weight 6n + \frac{3}{2}(3n + 1) and the vertices all have weight 3n + \frac{3}{2}(3n + 1). □

In the above construction, label 1 appears on an edge. If this edge is deleted, and 1 is subtracted from the label of each vertex and each remaining edge, the resulting labeling is totally magic, with vertex constant 3n + \frac{3}{2}(3n − 1) and edge constant 6n + \frac{3}{2}(3n − 1). This produces another infinite family:

Corollary 10.1 The graph P_{3} ∪ nK_{3} is totally magic when n is even.

On the other hand, an even union of triangles is never totally magic.

Theorem 11 There is no totally magic labeling of nK_{3}, the disjoint union of n triangles, whenever n is even.

Proof. Suppose λ is a totally magic labeling of nK_{3}, where n = 2m for some positive integer m. Write h and k for the vertex and edge constants of λ. If xyz is a triangle, write μ(x) for λ(yz).

Summing the weights of edges and vertices, we have ∑_{x}(λ(x) + 2μ(x)) = 6mh and ∑_{x}(μ(x) + 2λ(x)) = 6mk, so ∑_{x}(λ(x) + μ(x)) = 2m(h + k). Since the labels are 1, 2, …, 12m,

36m + 3 = h + k.  (8)

Consider a triangle xyz. Clearly λ(xy) = k − λ(x) − λ(y). So λ(x) + λ(xy) + λ(xz) = h implies λ(x) + k − λ(x) − λ(y) + k − λ(x) − λ(z) = h. So the sum of the three vertex labels is the same in any triangle:

λ(x) + λ(y) + λ(z) = 2k − h.

Similarly the sum of the three edge labels in a triangle is constant:

λ(xy) + λ(yz) + λ(zx) = 2h − k.

So λ(xy) = k − λ(x) − λ(y) = k + λ(z) − λ(x) − λ(y) − λ(z) = h − k + λ(z), or

λ(xy) = h − k + λ(x).  (9)

Let us assume that h ≥ k (otherwise, we can exchange the labels of the vertices and the edges and obtain another totally magic labeling with h ≥ k). Then from (9) labels 1, 2, …, h − k must all be vertex labels, and h − k + 1, h − k + 2, …, 2(h − k) are edge labels. So 2(h − k) + 1, 2(h − k) + 2, …, 3(h − k) are vertex labels, and so on: the vertex labels are precisely the labels a satisfying a ≡ 1, 2, …, (h−k)( mod 2(h−k)). Since there are 6m vertices and 6m edges, h − k divides 6m. Clearly h − k ≡ h + k = 36m + 3 ≡ 1(mod 2), so , h − k is odd, h − k divides 3m, and therefore 1 ≤ h − k ≤ 3m.

First, suppose h − k = 1. We have to partition the edge labels 2, 4, …, 12m into 2m sets of size 3 such that the sum of the labels in each set is constant. If such a partition exists, halving it provides a partition of 1, 2, …, 6m into 2m sets of size 3 such that the sum of the labels in each set is a constant. But such a partition is impossible by Lemma 9.

So we assume h−k ≥ 3. Write h−k = 2c+1. From (8) we obtain h = 18m+c+2 and k = 18m − c + 1. So 2k − h = 18m − 3c, and 2k − h ≡ 18m − 3c ≡ −3c ≡ c + 2(mod 4c + 2), since 2c + 1 divides 3m.

Each vertex label must be congruent to one of 1, 2, …, h − k(mod 2(h − k)), that is 1, 2, …, 2c + 1(mod 4c + 2). The sum of the three vertex labels in any triangle will be congruent to 2k − h. Now, 2k − h ≡ c + 2(mod 4c + 2). Since 0 < c < h − k, c + 1 must be a vertex label. But this is impossible, since there do not exist two elements d, e ∈ {1, 2, …, 2c + 1}( mod 4c + 2) such that c + 1 + d + e ≡ c + 2(mod 4c + 2).

Hence 2mK_{3} is not totally magic for any positive integer m. □

If there were a totally magic labeling of P_{3} ∪ nK_{3} with vertex and edge constants h and k, it is easy to show that the labels on the endpoints of the P_{3} must add to k. Suppose those two endpoints are joined, and the new edge is labeled 0. Then the labeling of (n + 1)K_{3}, constructed by adding 1 to every label, will be totally magic. From Theorem 11, this cannot occur when n is odd. So

Corollary 11.1 The graph P_{3} ∪ nK_{3} is not totally magic when n is odd.

6 Small graphs

We have carried out a complete search for small totally magic graphs. The result is that no examples with ten or fewer vertices exist, other than the four graphs given in Section 2 and the two nine-vertex graphs constructed in Theorem 10 and Corollary 10.1.

The complete search was carried out in two stages. First, using nauty [5], lists were prepared of all connected graphs (up to ten vertices) not ruled out by Theorems 5, 6, 7 and 8. Second, the survivors were tested exhaustively. There were three survivors with six or fewer vertices (K_{1}, K_{3} and P_{3}), 42 with seven, 1,070 with eight, 61,575 with nine and 4,579,637 with 10.

Exhaustive testing is very time-consuming. However, a shortcut is available. If a totally magic labeling exists, it must retain the magic properties after reduction modulo 2. So we tested all mod 2 possibilities. Label 1 or 0 is assigned to each vertex and to the constant k. Then every edge-label can be calculated. Next, one can check whether all the vertex weights are congruent (mod 2). Moreover, the total number of vertices and edges labeled 1 must either equal the number labeled 0 or exceed that number by 1. This process is quite fast (for example, only 2^{9} cases need to be examined in the eight-vertex case), and eliminated over 25% of graphs. Then one can sieve the remaining graphs modulo 3, then modulo 4, and so on. For example, sieving the 1070 eight-vertex graphs mod2 eliminated 307 graphs, sieving mod3 eliminated 351 more, and so on: one graph survived after sieving modulo 7, and it was eliminated mod 8.

There were very few disconnected graphs to consider. Except for the graph K_{1} ∪ P_{3}, the only possibilities are made up of at most one star, copies of K_{3}, and survivors with more than three vertices. The only cases not already discussed are K_{1,n} ∪ K_{3} for n = 3, 4, 5, 6, K_{1,4} ∪ 2K_{3}, and the 42 unions of a triangle and a 7-vertex survivor. None of these is totally magic, so there are no further totally magic graphs with ten or fewer vertices.

There are exactly eight totally magic labelings of 3K_{3}. They arise in dual pairs (the dual is derived by exchanging the label of each vertex with that of its opposite edge). Of the four pairs, two come from the construction of Theorem 10 and two do not. In each dual pair, one member has 1 as an edge label, so there are four totally magic labelings of P_{3} ∪ 2K_{3}.

We carried out a further investigation using a variant of simulated annealing. This procedure quickly found the graphs we have described, but has so far found no other examples. This might suggest that we have found all totally magic graphs. However, for larger numbers of vertices (more than 20, say), it appears that the search gets “nearer” to satisfaction (no, we do not wish to clarify this vague description!), so perhaps there are large totally magic graphs yet to be discovered.

References

[1] E. T. Baskaro, M. Miller, Slamin and W. D. Wallis, Edge-Magic Total Labelings, Austral. J. Combin. 22 (2000), 177–190.

[2] J. A. Gallian, A dynamic survey of graph labeling, Electronic J. Combinatorics 5 (1998), #DS6.

[3] A. Kotzig and A. Rosa, Magic valuations of finite graphs. Canad. Math. Bull. 13 (1970), 451–461.

[4] J. MacDougall, M. Miller, Slamin and W. D. Wallis, Vertex-magic total labelings. Utilitas Math., to appear.

[5] B. D. McKay, nauty User’s Guide (version 1.5). Technical Report TR-CS-87-03 (Department of Computer Science, Australian National University, 1990).

[6] W. D. Wallis A Beginner’s Guide to Graph Theory. (Birkhauser, Boston, 2000).