Labelling Wheels for Minimum Sum Number

Mirka MILLER  Joseph RYAN
Department of Computer Science  Department of Mathematics
University of Newcastle, NSW 2308, Australia  University of Newcastle, NSW 2308, Australia

e-mail: mirka@cs.newcastle.edu.au  e-mail: joe@math.newcastle.edu.au

SLAMIN  William F. SMYTH
Department of Computer Science  Department of Computer Science and Systems
University of Newcastle, NSW 2308, Australia McMaster University, Hamilton, Ontario, Canada

e-mail: slamin@cs.newcastle.edu.au  e-mail: smyth@mcmaster.ca

School of Computing, Curtin University Bentley, WA 6102, Australia

Abstract

A simple undirected graph G is called a sum graph if there exists a labelling L of the vertices of G into distinct positive integers such that any two distinct vertices u and v of G are adjacent if and only if there is a vertex w whose label L(w) = L(u) + L(v). It is obvious that every sum graph has at least one isolated vertex, namely the vertex with the largest label. The sum number σ(H) of a connected graph H is the least number r of isolated vertices \overline{K_{r}} such that G = H +\overline{K_{r}} is a sum graph. It is clear that if H is of size m, then σ(H) ≤ m. Recently Hartsfield and Smyth showed that for wheels W_{n} of order n+1 and size m = 2n, σ(W_{n}) ∈ Θ(m); that is, that the sum number is of the same order of magnitude as the size of the graph. In this paper we refine these results to show that for even n ≥ 4, σ(W_{n}) = n/2 + 2, while for odd n ≥ 5 we disprove a conjecture of Hartsfield and Smyth by showing that σ(W_{n}) = n. Labellings are given that achieve these minima.

1 Introduction

Since the introduction of sum graphs by Harary [4], there have been several papers specifying or bounding the sum number of particular classes H of graphs: complete graphs [1], complete bipartite graphs [5], complete multipartite graphs [7], and trees [2]. In all of these cases, σ(H) ∈ Θ(m/n), where n is the order (number of vertices) and m the size (number of edges) of H; that is, the order of magnitude of the sum number is at most the order of the graph. It is known however [3] that there exist classes H of graphs such that σ(H) ∈ Θ(n^{2}), even though no such graphs have yet been constructed. A step in the direction of constructing such graphs was taken by Hartsfield and Smyth [6], who showed that for wheels W_{n}, σ(W_{n}) ∈ Θ(m). Wheels are thus graphs of some interest in this context, and in this paper we extend the results of [6] to give labellings for all wheels that achieve the minimum sum number.

In Section 2 of this paper we show that for even n ≥ 4, σ(W_{n}) = \frac{n}{2} + 2, thus correcting an error in [6]. In Section 3 we show that for odd n ≥ 5, σ(W_{n}) = n, disproving the conjecture in [6] that σ(W_{n}) = n + 2. This latter result depends on a recent paper [8] that deals with a closely-related problem, the “integral sum number” of cycles.

2 Even Wheels

For every integer n ≥ 3, a wheel W_{n} is the graph defined by a pair of sets (V, E), where V = {c, v_{0}, v_{1}, ..., v_{n−1}} and E = {(c, v_{i}), (v_{i}, v_{i+1})|i = 0, 1, ..., n − 1}. The vertex c is called the centre of the wheel, each edge (c, v_{i}), for i = 0, 1, ..., n − 1, is called a spoke, and the cycle C_{n} = W_{n} − c is called the rim. To simplify presentation, arithmetic on the indices of the vertices is interpreted modulo n, and we suppose that the vertices of V are already identified by their labels.

In a sum graph G, a vertex w is said to label an edge (u, v) if and only if w = u + v. The multiplicity of w, denoted by μ(w), is defined to be the number of edges which are labelled by w. If μ(w) > 0, then w is called a working vertex. If G = H + \overline{K_{r}} and H contains no working vertices, then G is said to be exclusive; otherwise, G is said to be inclusive. One of the interesting results of Hartsfield and Smyth [6] is that for n odd every sum graph G = W_{n} + \overline{K_{r}} is exclusive, while for n even every sum graph G = W_{n} + \overline{K_{r}} is inclusive.

The following lemmas will be useful for determining the sum number of even wheels. Proofs may be found in [6].

Lemma 1 Suppose that G = W_{n} + \overline{K_{r}} is a sum graph. If for some integer i satisfying 0 ≤ i ≤ n − 1, c + v_{i} ∈ V, then

(a) n is even;

(b) the vertices of the rim consist of \frac{n}{2} working vertices c + u_{j}, 1 ≤ j ≤ \frac{n}{2}, which label spokes, alternating with \frac{n}{2} vertices u_{k}, 1 ≤ k ≤ \frac{n}{2}, which do not label spokes. □

Lemma 2 Suppose that G = W_{n} + \overline{K_{r}} is a sum graph. Then no edge of the rim is labelled by a vertex of V. □

Lemma 3 There are at least three distinct edge labels on the rim of W_{n}. □

The first lemma allows us to label the vertices on the rim of W_{n}, for n even, alternating \frac{n}{2} working vertices with \frac{n}{2} nonworking vertices. The second and third lemmas imply that there are at least \frac{n}{2} + 3 isolated vertices required for G = W_{n}+\overline{K_{r}} to be a sum graph unless there exists an isolated vertex that labels both a spoke and an edge of the rim. The following theorem shows that no more than two such isolated vertices can exist in G if a minimum sum number is to be achieved.

Theorem 1 For n even, σ(W_{n}) ≥ \frac{n}{2} + 2. □

Proof Consider a vertex t which labels both a spoke (u, c) and an edge (v_{1}, v_{2}) of the rim. Then t = v_{1} + v_{2} = u + c and by Lemma 2, t is isolated. Since G is inclusive, it follows from Lemma 1 that the vertices on the rim are alternately working and nonworking. So without loss of generality we may consider v_{2} to be a working vertex; i.e., v_{2} = v′_{2} + c where v′_{2} is a nonworking vertex on the rim. We note also that u is a working vertex (else u + c would be on the rim) and may thus be expressed u′ + c. It follows from the expression for t that u = u′+c = v_{1}+v′_{2}. This seems to indicate that v_{1} is adjacent to both v_{2} and v′_{2}, in contradiction to the condition of alternating working and nonworking vertices. The only labelling that manages to avoid such a contradiction is v_{1} = v′_{2}, so that v_{2} = v_{1} + c and (v_{1}, v_{1} + c) is an edge of the rim.

Now let us redefine v_{2} to be the other nonworking vertex v_{2} ≠ v_{1} adjacent to v_{1} + c. Then from the definition of a sum graph, v_{2} + c is adjacent to v_{1}. Similarly, the nonworking vertex v_{3} ≠ v_{1} adjacent to v_{2} + c implies the existence of a working vertex v_{3} + c adjacent to v_{2}. We see that if 4 divides n, the rim vertices break down into two paths (v_{1}, v_{2} + c, v_{3}, …, v_{n/2} + c) and (v_{1} +c, v_{2}, v_{3} +c, …, v_{n/2}), while otherwise the paths are (v_{1}, v_{2} +c, v_{3}, …, v_{n/2}) and (v_{1} + c, v_{2}, v_{3} + c, …, v_{n/2} + c). Such labellings are called contrary. We see that a contrary labelling includes exactly two nonworking vertices v_{1} and v_{n/2} that are adjacent to their corresponding working vertices, and that these adjacent pairs are antipodal.

So far we have shown that it may be possible to reduce the sum number of G by one (to \frac{n}{2} + 2) by introducing the vertex t. It is clear that there can exist no more than two isolated vertices that label both spokes and edges of the rim. We show now that introducing a second such isolated vertex cannot reduce the sum number any further.

Suppose that there exists a second vertex s that labels both a spoke and an edge of the rim. Then since t = 2v_{1} + c, it follows that s = 2v_{n/2} + c, and so there exist two rim vertices 2v_{1} and 2v_{n/2}. It follows that n > 4. Now let x ≠ v_{1} and y ≠ v_{n/2} denote the two other nonworking vertices adjacent to v_{1} + c and v_{n/2} +c respectively. In order to label the edges of the rim, there must therefore exist vertices that are labelled with at least the following four sums:

2v_{1} + c, v_{1} + x + c, 2v_{n/2} + c, v_{n/2} + y + c.

Further, in order to reduce the number of distinct sums to three, and so to achieve sum number \frac{n}{2} + 1, at least one pair of these sums must be identical. The only possibilities are 2v_{1} + c = v_{n/2} + y + c and 2v_{n/2} + c = v_{1} + x + c. But the first of these implies that 2v_{1} = v_{n/2} + y and so, since 2v_{1} is a vertex, we conclude that (v_{n/2}, y) is an edge, an impossibility. Similarly the second case is impossible, and it follows therefore that there must exist at least four isolated vertices corresponding to edges of the rim. Thus the sum number of G cannot be reduced below 2n + 2 by introducing s. □

We use the ideas in this result to construct a labelling for W_{n}, n even, that achieves σ(W_{n}) = \frac{n}{2} + 2. Letting n = 2l, we consider the vertices around the rim as two disjoint paths of length l − 1, P_{1} and P_{2} , one clockwise in direction and the other counterclockwise. The centre is labelled by c, while the two paths are labelled as shown below with the parameters c, x and d, all arbitrary at this stage. Later we will formulate x in terms of d and c and give conditions under which these labels will provide a sum numbering. Let

P_{1} = (x, 2x, x − d + c, 2x + d − c, x − 2d + 2c, 2x + 2d − 2c, ..., y);
P_{2} = (x + c, 2x − c, x − d + 2c, 2x + d − 2c, x − 2d + 3c, 2x + 2d − 3c, ..., z),

where for l even

y = 2x + (\frac{l − 2}{2})d − (\frac{l − 2}{2})c;
z = 2x + (\frac{l − 2}{2})d − (\frac{l}{2})c;

while for l odd

y = x − (\frac{l − 1}{2})d + (\frac{l − 1}{2})c;
z = x − (\frac{l − 1}{2})d + (\frac{l + 1}{2})c.

Alternatively,

P_{1} = \{(\frac{3 + (−1)^{m}}{2} )x + (−1)^{m}(⌈\frac{m}{2}⌉ − 1)d − (−1)^{m}(⌈\frac{m}{2}⌉ − 1)c\}_{m=1}^{l};

P_{2} = \{(\frac{3 + (−1)^{m}}{2} )x + (−1)^{m}(⌈\frac{m}{2}⌉ − 1)d − (−1)^{m}(⌈\frac{m}{2}⌉)c\}_{m=1}^{l} .

In each path, each pair of adjacent vertices sum to, alternately, 3x and 3x−d+c constributing 2 isolates to the sum number. Note that when l is even, 3x appears \frac{l}{2} times in each path, while 3x − d + c appears \frac{l−2}{2} times, indicating that the final sum is 3x. When l is odd, both sums appear \frac{l−1}{2} times and the final sum is 3x − d + c. We now construct the rim by connecting the two paths in a way that does not require the inclusion of any extra isolates.

Joining the two initial vertices in each path requires a vertex 2x + c taking advantage of an already existing isolate that corresponding to the the spoke (2x, c). When joining the final vertices, we note that the induced sum must be different to the final sums in each path. So for l even, this final sum must be 3x − d + c, while for l odd it is 3x. Therefore for l even we have

(2x + (\frac{l − 2}{2})d − (\frac{l − 2}{2})c) + (2x + (\frac{l − 2}{2})d − (\frac{l}{2})c) = 3x − d + c

or

4x + (l − 2)d − (l − 1)c = 3x − d + c

that is,

x = lc − (l − 1)d;

while for l odd we have

(x − (\frac{l − 1}{2})d + (\frac{l − 1}{2})c) + (x − (\frac{l − 1}{2})d + (\frac{l + 1}{2})c) = 3x

or

2x − (l − 1)d + lc = 3x

again yielding,

x = lc − (l − 1)d.

The construction above provides at most l + 2 isolated vertices,

\overline{K_{r}} = \{x + 2c, 2x + c, x − d + 3c, 2x + d, x − 2d + 4c, 2x + 2d − c, ..., w\}
∪ {3x − d + c, 3x}

where

w = \{ \begin{matrix}2x + (\frac{l−2}{2})d − (\frac{l−4}{2})c, & for l even; \\ x − (\frac{l−1}{2})d + (\frac{l+3}{2})c, & for l odd. \end{matrix}

Alternatively,

\overline{K_{r}} = \{(\frac{3 + (−1)^{m}}{2} )x + (−1)^{m}(⌈\frac{m}{2}⌉ − 1)d + (\frac{(−1)^{m}(1 − 2⌈\frac{m}{2}⌉) + 3}{2})c\}_{m=1}^{l}
∪ {3x − d + c, 3x}.

We observe further that by choosing x = lc − (l − 1)d, c = 1, and d = −l, we can easily ensure that the construction gives a sum graph whose sum number is at most \frac{n}{2} + 2. By Theorem 1 the sum number is at least \frac{n}{2} + 2 and so we have established

Theorem 2 For n even, σ(W_{n}) = \frac{n}{2} + 2. □

3 Odd Wheels

In this section we disprove the conjecture of Hartsfield and Smyth [6] that for odd n ≥ 7, σ(W_{n}) = n+2 by showing that for odd n ≥ 5, σ(W_{n}) = n. We begin by noting once again the result [6] that for odd n, every sum graph G = W_{n}+\overline{K_{r}} is exclusive. This obviously implies that at least n isolated vertices are required for G = W_{n} + \overline{K_{r}} to be a sum graph. To achieve the minimum sum numbering, we construct the labelling of W_{n} for n odd based on a recent paper [8] that deals with a closely related problem, the integral sum number of cycles.

A simple undirected graph G is called an integral sum graph if there exists a labelling λ of the vertices of G into distinct integers such that any two distinct vertices u and v of G are adjacent if and only if there is a vertex w whose label λ(w) = λ(u) + λ(v). Thus the main difference between the integral sum graph and the sum graph is that the integral sum graph uses distinct integers for labelling, whereas the sum graph uses distinct positive integers. The integral sum number ζ(H) is the least number of isolated vertices \overline{K_{r}} such that G = H + \overline{K_{r}} is an integral sum graph.

In [8] Sharary showed that the integral sum number of cycles is given by

ζ(C_{n}) = \{ \begin{matrix}0 & if n ≠ 4 \\ 3 & if n = 4. \end{matrix}

To obtain ζ(C_{n}) = 0 for odd n, the vertices of the cycle C_{n} can be labelled as follows.

\begin{aligned}n = 3 & ⇒ & V = \{−1, 0, 1\}; \\ n = 5 & ⇒ & V = \{1, 2, −1, 3, −2\}; \\ n = 7 & ⇒ & V = \{4, 3, 1, 2, −5, 7, −3\}; \\ n = 9 & ⇒ & V = \{−1, −3, −4, 1, −15, 8, −7, 15, −14\}; \\ n = 11 & ⇒ & V = \{−1, 4, 3, 1, −23, 15, −8, 7, −6, 21, −22\}; \\ n ≥ 13 & ⇒ & V = \{b_{1}, b_{2}, ..., b_{n−2}, d_{n−1}, d_{n}\}, \end{aligned}

where

b_{1} = 4;
b_{2} = 1;
b_{i} = b_{i−2} − b_{i−1} for i = 3, 4, ..., n − 2;
d_{n−1} = b_{1} + b_{2} − b_{n−2} = 5 − b_{n−2}; and
d_{n} = b_{n−2} − b_{1} = b_{n−2} − 4.

Lemma 4 Let a_{i}, i = 1, 2, …, n, denote the labels of the vertices under the integer sum labelling λ that achieves ζ(C_{n}) = 0. Then L = λ + c where c ≥ 3| min_{i=1}^{n}{a_{i}}|+1 is a sum labelling of W_{n} for odd n ≥ 5 with n isolated vertices.

Proof Let v_{i}, for every i = 1, 2, ..., n, be the labels of vertices around the rim of W_{n} and c be the label of the centre of W_{n}. Let v_{i} = 3a_{i} + c, for every i = 1, 2, ..., n. Then

\begin{matrix}v_{i} + c = 3a_{i} + 2c; and \\ v_{i} + v_{i+1} = 3(a_{i} + a_{i+1}) + 2c. \end{matrix}

Let R be the set of isolated vertices which label the spokes and S be the set of isolated vertices which label the rim. Then

\begin{matrix}R = \{3a_{i} + 2c|i = 1, 2, ..., n\}; and \\ S = \{3(a_{i} + a_{i+1}) + 2c|i = 1, 2, ..., n\}. \end{matrix}

For n ∈ {5, 7, 9, 11}, we can see that S ⊂ R and so that S ∪ R = R. Therefore

\overline{K_{n}} = R = \{3a_{i} + 2c|i = 1, 2, ..., n\}.

Similarly, for odd n ≥ 13 this construction gives

R = {3a_{i} + 2c|i = 1, 2, ..., n}.

The set S can be obtained in the following way.

For i = 3, 4, ..., n − 2,

v_{i−1} + v_{i} = 3a_{i−2} + 2c

while

\begin{aligned}v_{n−2} + v_{n−1} & = & 3a_{5} + 2c; \\ v_{n−1} + v_{n} & = & 3a_{2} + 2c; \\ v_{n} + v_{1} & = & 3a_{n−2} + 2c; \\ v_{1} + v_{2} & = & 3a_{5} + 2c. \end{aligned}

Then

S = {3a_{i} + 2c|i = 1, 2, ..., n − 4} ∪ {3a_{n−2} + 2c}.

Note that S ⊂ R. Therefore

\overline{K_{n}} = R = \{3a_{i} + 2c|i = 1, 2, ..., n\}. □

We note that for n = 3 any minimal integral labelling of C_{3} must contain 0 as a label which means that using the above construction for W_{3} would result in one of the vertices on the rim having the same label as the centre which is not allowed. In fact, W_{3} ≅ K_{4} and so σ(W_{3}) = σ(K_{4}) = 5.

We have established

Theorem 3 For odd n ≥ 5, σ(W_{n}) = n. □

Acknowledgements

The work of the fourth author was supported by Grant No. A8180 of the Natural Sciences & Engineering Research Council of Canada and by Grant No. GO-12778 of the Medical Research Council of Canada.

References

[1] D. Bergstrand, F. Harary, K. Hodges, G. Jennings, L. Kuklinski & J. Wiener, The sum number of a complete graph, Bull. Malaysian Math. Soc. 12 (1989) 25-28.

[2] Mark N. Ellingham, Sum graphs from trees, Ars Combinatoria 35 (1993) 335-349.

[3] R. Gould & V. Rödl, Bounds on the number of isolated vertices in sum graphs, Graph Theory, Combinatorics and Applications (edited by Y. Alevi, G. Chartrand, O. R. Oellermann & A. J. Schwenk), John Wiley & Sons (1991) 553-562.

[4] F. Harary, Sum graphs and difference graphs, Congressus Numerantium 72 (1990) 101-108.

[5] Nora Hartsfield & W. F. Smyth, The sum number of complete bipartite graphs, Graphs and Matrices (edited by Rolf Rees), Marcel Dekker (1992) 205-211.

[6] Nora Hartsfield & W. F. Smyth, A family of sparse graphs of large sum number, Discrete Math. 141 (1995) 163-171.

[7] Joseph Ryan, Mirka Miller & W. F. Smyth, The sum labelling for the cocktail party graph, submitted for publication.

[8] Ahmad Sharary, Integral sum graphs from complete graphs, cycles and wheels, Arab Gulf J. Sci. Res. 14-1 (1996) 1-14.