On the Spectra of Totally Magic Labelings

J. P. McSorley and W. D. Wallis Department of Mathematics Southern Illinois University Carbondale, IL 62901-4408, USA

Abstract

A totally magic labeling of a graph with v vertices and e edges is a one-to-one map taking the vertices and edges onto the integers 1, 2, ⋯, v + e, such that the sum h of the label on a vertex and the labels on its incident edges is a constant independent of the choice of vertex, and the sum k of an edge label and the labels of the endpoints of the edge is constant. Such graphs appear to be rare. In this paper we examine the possible labelings of a union of an odd number of triangles, and determine the spectrum of possible values h, k for all known totally magic graphs.

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 totally magic labeling λ on a graph 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, and given any edge xy,

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

for some constant k. A graph having a totally magic labeling is called a totally magic graph.

Totally magic labelings have been discussed in [1]. It is shown in that paper that totally magic graphs are very rare. The only known infinite families consist of the unions of an odd number of triangles, mK_{3}, where m is odd, and the same graphs with precisely one edge deleted. (On the other hand, the members of these families with m even are never totally magic.)

We define the spectrum of a totally magic graph to be the set of pairs of values (h, k) that arise as vertex and edge constants in totally magic labelings of the graph. We shall determine the spectra of the members of the above two infinite families, showing that there is a labeling for every h and k not excluded by simple arithmetical considerations.

Constructions

In this paper we examine labelings of mK_{3} is detail. (This extends the discussion in Section 5 of [1].) Suppose λ is a totally magic labeling of mK_{3}, with vertex and edge constants h and k. We know that m is odd. Suppose the vertices of one of the triangles are labeled x, y, z; suppose the edge opposite the vertex labeled x receives the label X, and so on. Then

h = x + Y + Z = X + y + Z = X + Y + z,  (1)

k = X + y + z = x + Y + z = x + y + Z.  (2)

If we write s = x + y + z and S = X + Y + Z, then (1) and (2) yield

3h = 2S + s,
3k = S + 2s,
h + k = S + s.

So

3h − 3k = S − s,

whence

S = 2h − k,
s = 2k − h.

Finally, from X + Y + Z = S and x + Y + Z = h we obtain

X − x = S − h = h − k  (3)

for every choice of x, that is the difference between an edge label and the opposite vertex label is a constant, h − k.

Let us write d for h − k. It is clear that h and k determine d. On the other hand, if d is known, then h and k are determined. For each triangle,S + s = h + k, so summing over all triangles we get m(h + k). But this is the sum of all vertex and edge labels in mK_{3}, so it equals \frac{1}{2}6m(6m + 1), and h + k = 3(6m + 1). Therefore

h = 9m + \frac{1}{2}(3 + d) and k = 9m + \frac{1}{2}(3 − d).  (4)

Without loss of generality, let us assume k < h, that is d = h − k > 0. (k = h is impossible, as it would imply x = X, and if k > h then we can obtain a dual labeling with k < h by interchanging the labels on each vertex and its opposite edge.) From (3), every edge label is at least d + 1, and 1, 2, …, d are all vertex labels. The edges opposite those vertices receive labels d + 1, d + 2, …, 2d. Proceeding in this way, we see that the set of vertex labels is

T_{d}(m) = {1, 2, …, d, 2d + 1, 2d + 2, …, 3d, 4d + 1, …, 6m − d}

and the edge labels are

{d + 1, d + 2, …, 2d, 3d + 1, 3d + 2, …, 4d, 5d + 1, …, 6m}.

So 6m is a multiple of 2d. We have

Theorem 1 If there is a totally magic labeling of mK_{3}, then m is odd and the vertex and edge constants have the values

h = 9m + \frac{1}{2}(3 + d) and k = 9m + \frac{1}{2}(3 − d),  (4)

for some divisor d of 3m.

(The negative divisors d correspond to the labelings that are duals of those with positive d.)

Suppose d is a specified positive divisor of 3m. Let 3m = ad. Then the sum of the elements of T_{d}(m) is

ms = ∑_{i=1}^{d} ∑_{j=0}^{a−1}(2jd + i)

= ∑_{i=1}^{d}(a(a − 1)d + ai)
= a(a − 1)d^{2} + \frac{1}{2}ad(d + 1),
s = 3(a − 1)d + \frac{3}{2}(d + 1).  (5)

So the triples of vertex labels of triangles must form a partition of T_{d}(m) into m triples, each with sum (5). Conversely, any such partition will define a totally magic labeling with the constants (4).

Lemma 2 If m is an odd positive integer and d is any divisor of 3m, then there exists a partition of

T_{d}(m) = {1, 2, …, d, 2d + 1, 2d + 2, …, 3d, 4d + 1, …,
(2a − 2)d + 1, (2a − 2)d + 2, …, (2a − 1)d}

into m triples, each with sum (5), where a = 3m/d.

Proof. We use two families of 3×n arrays, n odd, which are denoted A_{n} and B_{n}, and are defined as follows. A_{n} has j-th column (j, n+2−2j, \frac{1}{2}(n−1)+j), where entries are reduced modulo n, if necessary, so that they lie in the range 1, 2, …, n. This array was used by Kotzig [2]. Each row is a permutation of \{1, 2, …, n\}, and each column sums to \frac{1}{2}(3n + 3). B_{n} is constructed from a copy of A_{n} by adding n to every entry in the second row and 2n to every entry in the third row, so each column has sum \frac{1}{2}(9n + 3).

First, suppose d is a multiple of 3. Form a master array M by subtracting 1 from each entry of A_{a} and multiplying by 2d. From each column of M we construct d/3 triples by adding each of the columns of B_{d/3}. It is easy to check that the a(d/3) = m triples form a partition of T_{d}(m). All the triples have the same sum, because both component arrays have constant column sum.

If d is not a multiple of 3, then a must be. In that case the master array is formed from B_{a/3}, again subtracting 1 and multiplying by 2d. The columns of A_{d} are added. □

Here is an illustration of the two constructions for the graph 15K_{3}.

M = [ \begin{matrix}0 & 18 & 36 & 54 & 72 \\ 72 & 36 & 0 & 54 & 18 \\ 36 & 54 & 72 & 0 & 18 \end{matrix} ] B_{d/3} = [ \begin{matrix}1 & 2 & 3 \\ 6 & 4 & 5 \\ 8 & 9 & 7 \end{matrix} ]

Partition

1 2 3 19 20 21 37 38 39 55 56 57 73 74 75
78 76 77 42 40 41 6 4 5 60 58 59 24 22 23
44 45 43 62 63 61 80 81 79 8 9 7 26 27 25

Example for a = 5, d = 9, m = 15, column sum 123.

M = [ \begin{matrix}0 & 10 & 20 \\ 50 & 30 & 40 \\ 70 & 80 & 60 \end{matrix} ] A_{d} = [ \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 1 & 4 & 2 \\ 3 & 4 & 5 & 1 & 2 \end{matrix} ]

Partition

1 2 3 4 5 11 12 13 14 15 21 22 23 24 25
55 53 51 54 52 35 33 31 34 32 45 43 41 44 42
73 74 75 71 72 83 84 85 81 82 63 64 65 61 62

Example for a = 9, d = 5, m = 15, column sum 129.

Theorem 3 There is a totally magic labeling of mK_{3} with vertex and edge constants h and k if and only if m is odd and h = 9m + \frac{1}{2}(3 + d) and k = 9m + \frac{1}{2}(3 − d), where d is a divisor of 3m.

Suppose λ is a totally magic labeling of mK_{3} corresponding to a negative divisor d of 3m, with vertex and edge constants h and k, and suppose edge u satisfies λ(u) = 1. Define μ(x) = λ(x) − 1 for each edge or vertex x. Delete edge u. Then μ is a totally magic labeling of P_{3} ∪ (m − 1)K_{3} with vertex and edge constants h − 3 and k − 3. This construction can be reversed, so totally magic labelings of P_{3} ∪ (m − 1)K_{3} are equivalent to totally magic labelings of mK_{3} in which 1 is an edge label — precisely those for which the divisor d is negative. Writing f = −d (to avoid negative divisors), we have

Theorem 4 There is a totally magic labeling of P_{3} ∪ (m − 1)K_{3} with vertex and edge constants h and k if and only if m is odd and h = 9m − \frac{1}{2}(f + 3) and k = 9m + \frac{1}{2}(f − 3), where f is a positive divisor of 3m.

Conclusion

The only known totally magic graphs not covered by Theorems 3 and 4 are the trivial case K_{1}, for which h = 1 and k is not defined, and K_{1} ∪ P_{3}, whose unique totally magic labeling has (h, k) = (6, 9) (see [1]). Thus we have completely determined the spectrum of every known totally magic graph.

References

[1] G. Exoo, A. C. H. Ling, J. P. McSorley, N. C. K. Phillips and W. D. Wallis, Totally magic graphs. (to appear).

[2] A. Kotzig, On magic valuations of trichromatic graphs. Reports of the CRM CRM–148, December 1971.