A FAMILY OF SPARSE GRAPHS OF LARGE SUM NUMBER

Nora Hartsfield Department of Mathematics Western Washington University

W. F. Smyth Department of Computer Science & Systems McMaster University School of Computing Science Curtin University of Technology

ABSTRACT

Given an integer r ≥ 0, let G_{r} = (V_{r}, E) denote a graph consisting of a simple finite undirected graph G = (V, E) of order n and size m together with r isolated vertices \overline{K}_{r}. Then |V | = n, |V_{r}| = n + r, and |E| = m. Let L : V_{r} → ^{+} denote a labelling of the vertices of G_{r} with distinct positive integers. Then G_{r} is said to be a sum graph if there exists a labelling L such that for every distinct vertex pair u and v of V_{r}, (u, v) ∈ E if and only if there exists a vertex w ∈ V_{r} whose label L(w) = L(u) + L(v). For a given graph G, the sum number σ = σ(G) is defined to be the least value of r for which G_{r} is a sum graph. Gould and Rödl have shown that there exist infinite classes G of graphs such that, over G ∈ G, σ(G) ∈ Θ(n^{2}), but no such classes have been constructed. In fact, for all classes G for which constructions have so far been found, σ(G) ∈ o(m). In this paper we describe constructions which show that for wheels W_{n} of (sufficiently large) order n + 1 and size m = 2n, σ(W_{n}) = n/2 + 3 if n is even and n ≤ σ(W_{n}) ≤ n + 2 if n is odd. Hence for wheels σ(W_{n}) ∈ Θ(m).

1 INTRODUCTION

Sum graphs were introduced by Harary [Har88]. In 1989 Hao [Hao89] established a lower bound on σ(G) in terms of the degree sequence of G, and also showed that a sum graph of order n and size m exists if and only if

m ≤ \frac{\binom{n}{2} − ⌊\frac{n}{2}⌋}{2}.

These results have recently been applied by Smyth [S92] to unit graphs (that is, graphs G for which σ(G) = 1). He shows that there exists a unit graph of order n > 1 and size m if and only if ⌈n/2⌉ ≤ m ≤ ⌊n^{2}/4⌋, and provides a methodology for constructing at least one such graph for each suitable value of m. The same paper also shows how to construct graphs G of given order n ≥ 4 and size m whose sum number σ(G) ∈ o(m). Other constructions have been found for specific classes:

* Ellingham [E89] shows that every nontrivial tree is a unit graph;

Typeset by AMS-TEX

* Bergstrand et al. [BHHJKW89] show that for a complete graph K_{n}, n ≥ 4, σ(K_{n}) = 2n − 3;

* Hartsfield and Smyth [HS92] show that for a complete bipartite graph K_{p,q}, 2 ≤ p ≤ q, σ(K_{p,q}) = ⌈(3p + q − 3)/2⌉.

Thus to date constructions have focussed on sum graphs of “small” sum number: no class of graphs is known whose sum number is even close to the bound of Gould and Rödl [GR89] given in the Abstract. In this paper we consider wheels W_{n} of order n + 1 and size m = 2n; we show that, over all wheels W, σ(W_{n}) ∈ Θ(m). Section 2 shows that, for odd n, n ≤ σ(W_{n}) ≤ n + 2, and describes labellings which achieve the upper bound. Section 3 considers the case in which n is even, and presents a construction which achieves sum number σ(W_{n}) = n/2 + 3. Section 4 discusses some conjectures and open problems.

2 WHEELS WITH AN ODD NUMBER OF SPOKES

For every integer n ≥ 3, a wheel W_{n} = (V, E) is the graph defined by V = {c, a_{1}, a_{2}, …, a_{n}}, E = {(c, a_{i}), (a_{i}, a_{i+1})|i = 0, 1, …, n − 1}, where here and throughout this paper arithmetic on indices is interpreted modulo n. (Thus, for example, (n − 1) + 1 = 0.) The vertex c is called the center of the wheel, each edge (c, a_{i}), i = 0, 1, …, n − 1, is called a spoke, and the cycle C_{n} = W_{n} − c is called the rim. We let W = {W_{3}, W_{4}, …. } and, to simplify notation, we suppose that the vertices V are already identified by their labels (distinct positive integers) under L.

Some general sum graph terminology will be useful. In a sum graph G_{r}, a vertex u is said to label an edge (x, y) if and only if u = x+y. The number of edges labelled by a given vertex u is called its multiplicity and is denoted by μ(u); if μ(u) > 0 then u is said to be a working vertex. If G_{r} = G + \overline{K}_{r} and G contains no working vertices, then G_{r} is said to be exclusive; otherwise G_{r} is said to be inclusive. One of the interesting results of Bergstrand et al. [BHHJKW89] is that for n ≥ 4 every sum graph G_{r} = K_{n} + \overline{K}_{r} is exclusive. In this section we first show that every sum graph G_{r} = W_{n} + \overline{K}_{r} is exclusive provided n is odd.

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

(a) n is not odd;

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

Proof By hypothesis, there exists a_{j} ∈ V such that (a_{j}, c + a_{i}) ∈ E and j ≠ i. Then c + a_{j} and c + a_{j} + a_{i} are both vertices, so that (c + a_{j}, a_{i}) ∈ E and c + a_{j} ∈ V. Thus every working vertex c + a_{i} implies the existence of another working vertex c + a_{j} adjacent to a_{i}, and we see that (b) follows. Observe then that (b) cannot hold if n is odd. □

This result tells us that either there are no working vertices in V which label spokes or there are exactly n/2 of them. We shall see in the next section that the latter case can in fact occur when n is even.

Lemma 2.2 Suppose that G_{r} = W_{n} + \overline{K}_{r} is a sum graph. Then no edge of the

rim is labelled by a vertex of V.

Proof For n = 3, W_{n} = K_{n+1} and the result follows from the fact [BHHJKW89] that every labelling of the complete graph is exclusive. Then suppose that n ≥ 4 and that, for some choice of i, a_{i} + a_{i+1} ∈ V. Two cases now arise: either c = a_{i} + a_{i+1} or there exists an integer j ∉ {i, i + 1} such that a_{j} = a_{i}+a_{i+1}. Suppose the former. Then there exists a rim vertex a_{j} ≠ a_{i+1} such that (a_{i}, a_{j}) ∈ E, and therefore there exists a vertex a_{i} + a_{j} ∈ V_{r}. But it must also be true that a_{i} + a_{i+1} + a_{j} ∈ V_{r}, from which it follows that (a_{i} + a_{j}, a_{i+1}) ∈ E, and so a_{i} + a_{j} must be a rim vertex. Thus the first case implies the second. Suppose then that a_{j} = a_{i} + a_{i+1} ∈ V. It follows that {c + a_{i} + a_{i+1}, c + a_{i}, c + a_{i+1}} ⊆ V_{r}, hence that (c + a_{i}, a_{i+1}) ∈ E, (c + a_{i+1}, a_{i}) ∈ E. Then the rim contains a cycle (c + a_{i+1}, a_{i}, a_{i+1}, c + a_{i}) in which the vertices that label spokes do not alternate. This contradicts Lemma 2.1 and completes the proof. □

These two lemmas immediately yield

Theorem 2.1 For odd n, every sum graph G_{r} = W_{n} + \overline{K}_{r} is exclusive. □

This result allows us to express the set \overline{K}_{r} of isolated vertices as a union of two subsets: R = {a_{i} + a_{i+1} |i = 0, 1, …, n − 1}, which labels edges of the rim, and S = {c + a_{i} |i = 0, 1, …, n − 1}, which labels spokes. Since the elements of S must all be distinct, it follows that, for odd n, σ(W_{n}) ≥ n. However, it does not follow that σ(W_{n}) = 2n: there are two strategies available to us to reduce r, which we now describe. We can try to choose vertex labels so that

(a) for certain nonnegative integers i and j ∉ {i − 1, i},

c + a_{i} = a_{j} + a_{j+1};  … (2.1)

(b) for certain nonnegative integers i and j ∉ {i − 1, i, i + 1},

a_{i} + a_{i+1} = a_{j} + a_{j+1}.  … (2.2)

We consider first strategy (b). Observe that the best possible result that can be achieved using equations (2.2) is to give alternate edges of the rim the same label; that is, to choose labels so that

a_{0} + a_{1} = a_{2} + a_{3} = ⋯ = a_{n−3} + a_{n−2},
a_{1} + a_{2} = a_{3} + a_{4} = ⋯ = a_{n−2} + a_{n−1}.

Thus R would reduce to {a_{0} + a_{1}, a_{1} + a_{2}, a_{n−1} + a_{0}}, yielding a labelling for which r = n + 3. (In fact it turns out that, for odd n ≥ 7, the best that can be done using strategy (b) is r = n + 4.) We shall now consider a construction based on strategy (a) which yields r = n + 2.

In order to describe this construction, we first make the assumption that c < a_{i} for every i = 0, 1, …, n − 1. Then each equation (2.1) implies that both a_{i} > a_{j} and a_{i} > a_{j+1} hold, and the aggregate of such equations defines a partial order on the vertices of the rim. Let us say that a vertex a_{j} is dominated if it occurs on the right hand side of some equation (2.1). Then in order that the partial order should be consistent, there must exist at least one vertex, say a_{k}, which is not dominated. Call such a vertex exceptional. It follows that at most n − 2 of the equations (2.1) can be simultaneously satisfied, and in that case both of the unsatisfied equations must include the exceptional vertex a_{k} on the right hand side:

c + a_{i} ≠ a_{k−1} + a_{k}, c + a_{j} ≠ a_{k} + a_{k+1},

for some integers i and j. Thus the only possible way to improve on a labelling induced by n − 2 equations (2.1) would be to apply equation (2.2), setting a_{k−1} + a_{k} = a_{k} + a_{k+1}, an impossibility since a_{k−1} ≠ a_{k+1}. We conclude that if n − 2 of the equations (2.1) can be simultaneously satisfied, and if c is the least label of W_{n}, then the resulting labelling cannot be further improved.

To produce n−2 consistent equations (2.1), set j = i−2 for every i = 2, 3, ..., n−1; then

c + a_{2} = a_{0} + a_{1}, c + a_{3} = a_{1} + a_{2}, …, c + a_{n−1} = a_{n−3} + a_{n−2}.  … (2.3)

These equations can easily be solved in terms of a_{0}, a_{1} and c, yielding

a_{i} = a_{0}f_{i−1} + a_{1}f_{i} − (f_{i+1} − 1)c,  … (2.4)

for i = 2, 3, …, n − 1, where f_{i} is the ith Fibonacci number (f_{0} = 0, f_{1} = 1, f_{i} = f_{i−2} + f_{i−1} for every i > 1). The solutions (2.4) may also be rewritten in Fibonacci form as

a_{i} = a_{i−2} + a_{i−1} − c,  … (2.4a)

exhibiting the labels of the rim vertices as a monotone increasing sequence. Then the set of isolated vertices corresponding to (2.3) is

\overline{K}_{n+2} = S ∪ R = \{c + a_{i} | i = 0, 1, …, n − 1; a_{n−2} + a_{n−1}; a_{n−1} + a_{0}\}, … (2.5)

where the a_{i}, i = 2, 3, …, n − 1, satisfy (2.4). Call this construction C_{1}: it remains to be seen whether a_{0}, a_{1} and c can be chosen so that C_{1} yields a sum graph. It is clear that every edge of E is labelled by an element of (2.5); what needs to be shown is that no vertex of G_{n+2} = W_{n} + \overline{K}_{n+2} is a sum of any pair of vertices of G_{n+2} which do not form an edge.

Theorem 2.2 For odd n and choices c = 1, a_{0} = 10, a_{1} = 100, the construction

C_{1} defined by (2.5) yields a sum graph G_{n+2} = W_{n} + \overline{K}_{n+2}.

Proof It is easy to verify, using (2.4a), that for every i = 2, 3, …, n − 1, the sums a_{j} + a_{i}, j = 0, 1, …, i − 1, satisfy

a_{i} + 1 < a_{j} + a_{i} < a_{i+1} − 1;

and further that

a_{i+1} < a_{i} + (a_{i} + 1) < a_{i+2}.

From these inequalities, and from the monotonicity of the a_{i}, it follows that no vertex of V_{n+2} takes any of the values a_{j} + a_{i}, a_{j} + (a_{i} + 1), or 2a_{i} + 1, over the indices i and j specified above. Since clearly c does not give rise to any unwanted edges, the result follows. □

The construction C_{1} was based on choosing c to be the least label of V. It turns out, however, that if c is chosen to be a label of intermediate value in V, then up to n − 1 equations (2.1) may be consistent and in at least some cases a labelling can be found for which r = n or n + 1. For n = 3, C_{1} yields σ(W_{n}) = 5 by the result of Bergstrand et al. [BHHJKW89]. But for n = 5 the assignment

c = x, a_{1} = x + 5d, a_{2} = x + 2d, a_{3} = x + d, a_{4} = x + 4d, a_{5} = x

induces a sum graph G_{5} = W_{5} + \overline{K}_{5} for suitable choices of the integers x and d; hence σ(W_{5}) = 5. Similarly, for n = 9 we have found a labelling which yields G_{10} = W_{9}+\overline{K}_{10} (so that σ(W_{9}) ≤ 10), while for n = 7 it appears that C_{1} is optimal. We return to this subject briefly in Section 4. For now we restrict ourselves to a formal statement of the main result of this section:

Theorem 2.3 For odd n, n ≤ σ(W_{n}) ≤ n + 2. □

3 WHEELS WITH AN EVEN NUMBER OF SPOKES

We begin this section by looking again at Lemma 2.1 in the case that n is even. Suppose that we start to give the rim vertices alternating working and nonworking labels, as prescribed by the lemma. If we begin somewhere with a nonworking label b_{1}, then adjacent to b_{1} there exists a working label c + b_{2}. Therefore, elsewhere on the rim, there exists a label b_{2} adjacent to c + b_{1}. If the directed edges (b_{1}, c + b_{2}) and (c+b_{1}, b_{2}) are either both oriented clockwise or both oriented counterclockwise, then we say that they are harmonious; otherwise, we say that they are contrary. If all such pairs of directed edges on the rim are harmonious, we say that we have a harmonious labelling; conversely, if all such pairs are contrary, then we have a contrary labelling.

Lemma 3.1 The labelling of every inclusive sum graph G_{r} = W_{n} + \overline{K}_{r} is either

harmonious or contrary.

Proof It is easy to see that if one pair of edges is harmonious (respectively, contrary), then the edges adjacent to them must also be harmonious (respectively, contrary). □

This result tells us that there are exactly two strategies for choosing working rim labels when n is even. Further, it is easy to see that for a contrary labelling, there must exist exactly two edges, say (b_{1}, c + b_{1}) and (b_{n/2}, c + b_{n/2}), joining nonworking vertices to their corresponding working vertices. On the other hand, for a harmonious labelling, every pair b_{i} and c + b_{i} of corresponding vertices must be antipodal. It follows from these observations that, for n ≡ 2 (mod 4), both harmonious and contrary labellings are possible, while for n ≡ 0 (mod 4), an inclusive sum graph can only have a contrary labelling.

We consider first, therefore, for any even n ≥ 4, a contrary labelling of the rim. Then there exists a nonworking vertex, say x, which is adjacent to its corresponding working vertex x + c, and thus by Lemma 2.1 there must exist an isolated vertex 2x + c ∈ \overline{K}_{r}. Further, there exists a second vertex y adjacent to x such that y ≠ x + c. Using Lemma 2.2, we may without loss of generality set y = x − d + c for some non-zero integer d, and it follows that there must exist a second isolated vertex 2x−d+c ∈ \overline{K}_{r}. Observe now that these two isolated vertices could possibly be used to label alternating edges of the rim. If this were done, the vertices of the rim could be expressed as follows, in terms of two disjoint paths, one clockwise in direction, the other counterclockwise, around the rim:

\begin{matrix}(x, x − d + c, x + d, x − 2d + c, x + 2d, …, w) \\ (x + c, x − d, x + d + c, x − 2d, x + 2d + c, …, z) \end{matrix}  … (3.1)

where the terminating vertices w and z are given by

w = x − ⌊n/4⌋d + c, for n ≡ 0 (mod 4),

= x + ⌊n/4⌋d, for n ≡ 2 (mod 4); … (3.2)

z = x − ⌊n/4⌋d,  for n ≡ 0 (mod 4),

= x + ⌊n/4⌋d + c, for n ≡ 2 (mod 4). … (3.3)

Then a third distinct isolated vertex

w + z = 2x − 2⌊n/4⌋d + c, for n ≡ 0 (mod 4),

= 2x + 2⌊n/4⌋d + c, for n ≡ 2 (mod 4), … (3.4)

must exist to label the edge (w, z). As in Section 2, denote by R the set of isolated vertices which label the rim; then

R = (2x + c, 2x − d + c, 2x ± 2⌊n/4⌋d + c),  … (3.5)

where the ambiguous sign in the third element is governed by (3.4). Similarly, the set of isolated vertices labelling spokes is

S = (x−id+2c|i = 1, 2, …, ⌊n/4⌋; x+id+2c|i = 0, 1, …, ⌊(n−2)/4⌋)…. (3.6)

Let C_{0} denote the construction described by (3.1)-(3.6). Clearly C_{0} yields vertices which provide labels for every edge of W_{n} and includes at most

|R| + |S| = n/2 + 3

isolated vertices. Observe further that by choosing (for example)

x = 10^{n}, d = 2n, c = 1,  … (3.7)

we can easily ensure that C_{0} yields a sum graph; that is, that for every pair of vertices u, v ∈ V ∪ R ∪ S such that (u, v) ∉ E, u + v ∉ V ∪ R ∪ S. We have then

Theorem 3.1 For even n ≥ 4, the construction C_{0} defined by (3.1)-(3.6) with labels (3.7) yields a sum graph G_{n/2+3} = W_{n} + \overline{K}_{n/2+3}. □

We consider now the question of whether or not C_{0} is optimal — that is, yields a minimum number of isolated vertices. First observe that every exclusive sum graph derived from W_{n} must contain at least n isolated vertices. For the special case n = 4 we leave it as an exercise for the reader to show that σ(W_{4}) = 5. For n ≥ 6 the fact that n ≥ n/2 + 3 tells us that C_{0} is at least as good as any construction based on an exclusive labelling. Moreover, in view of Lemmas 2.1 and 2.2, we see that, at least for contrary labellings, the only possible strategy to reduce the number of isolated vertices below n/2+3 is to label the vertices in such a way that at least one isolated vertex labels both a spoke and a vertex of the rim. The following lemma shows that such a strategy is impossible, no matter whether the labelling of the rim is harmonious or contrary.

Lemma 3.2 No vertex of an inclusive sum graph G_{r} = W_{n} + \overline{K}_{r} labels both a spoke and an edge of the rim.

Proof Suppose on the contrary that there exists a vertex t which labels both a spoke (c, y) and an edge (x_{1}, x_{2}) of the rim. Then t = x_{1} + x_{2} = y + c and, by Lemma 2.2, t is isolated. Since G_{r} is inclusive, it follows from Lemma 2.1 that the rim of W_{n} consists of alternating working and nonworking vertices. Therefore we may without loss of generality suppose that x_{2} = x′_{2} + c, where x′_{2} is a vertex of the rim. Observe also that if y is nonworking, then t = y +c is on the rim, a contradiction. Hence y = y′ +c is a working vertex corresponding to a nonworking vertex y′ of the rim.

From the above expression for t, it follows now that y = y′ + c = x_{1} + x′_{2}, from which we conclude that (x_{1}, x′_{2}) is an edge joining two nonworking vertices, in contradiction to the assumption that G_{r} is inclusive. □

Lemma 3.2 establishes the optimality of C_{0} in the case that n ≡ 0 (mod 4), when no harmonious labelling exists. But for n ≡ 2 (mod 4) it is easy to see that there exists no harmonious labelling with less than three distinct labels for rim edges. Thus we have established

Theorem 3.2 For even n, σ(W_{n}) = n/2 + 3. □

4 REMARKS

The results and conjectures of the preceding two sections establish the fact that for wheels the sum number is of the same order of magnitude as the number of edges. Wheels are the first class of graphs for which this property has been proven to hold, even though the existence of such classes has been established by [GR89]. Our results are not complete, however: for odd n, we have been able only to bound the sum number between n and n + 2. The exact computation of σ(W_{n}) in this case appears to be a rather difficult problem, to which we are able to contribute only the following

Conjecture 4.1 For n ≡ 1 (mod 4) and n ≥ 5, σ(W_{n}) = n + 1; for n ≡ 3 (mod 4), σ(W_{n}) = n + 2. □

Indeed, the fact that results for wheels have been rather difficult to establish, even given the generous structural information provided by Lemmas 2.1, 2.2, and 3.1, attests to the difficulty of sum number problems in general. In particular, it would be of great interest to determine a class of dense graphs for which the sum number is of the same order of magnitude as the size. Here also we make a conjecture:

Conjecture 4.2 For every integer n ≥ 2, let O_{2n} denote the generalized octohedron — that is, K_{2n} less a 1-factor. Then over all octahedra, σ(O_{2n}) ∈ Θ(n^{2}). □

It turns out that every sum graph derived from O_{2n} must be exclusive; but as for wheels this structural information is not sufficient to easily give rise to optimal constructions.

Finally, we mention an important conjecture for graphs of small sum number, first stated in [H89]:

Conjecture 4.3 Any disjoint union of unit graphs is a unit graph. □

This conjecture is known to hold for trees [E89].

REFERENCES

[BHHJKW89] D. Bergstrand, F. Harary, K. Hodges, G. Jennings, L. Kuklinski & J. Wiener, The sum number of a complete graph, to appear.

[E89] M. N. Ellingham, Sum graphs from trees, submitted for publication.

[GR89] R. Gould & V. Rödl, Bounds on the number of isolated vertices in sum graphs, to appear.

[Hao89] T. Hao, On sum graphs, Journal of Combinatorial Mathematics & Combinatorial Computing 6 (1989) 207-212.

[Har88] F. Harary, Sum graphs and difference graphs, presentation at the Nineteenth Southeastern Conference on Combinatorics, Graph Theory & Computing.

[HS92] N. Hartsfield & W. F. Smyth, The sum number of complete bipartite graphs, to appear.

[S92] W. F. Smyth, Sum graphs of small sum number, to appear.

ACKNOWLEDGEMENT

The work of the second author was supported in part by Grant No. A8180 of the Natural Sciences & Engineering Research Council of Canada.