SUM GRAPHS OF SMALL SUM NUMBER

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, E) denote a graph consisting of a simple finite undirected connected nontrivial graph G together with r isolated vertices \overline{K}_{r}. Let L : V → ℤ^{+} 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, (u, v) ∈ E if and only if there exists a vertex w ∈ V whose label L(w) = L(u) + L(v). For a given subgraph G, the sum number σ = σ(G) is defined to be the least number r for which G_{r} is a sum graph; in particular, if G_{1} = G ∪ \overline{K}_{1} is a sum graph, then the subgraph G is called a unit graph. In this paper it is shown that there exist graphs of every order n and size m whose sum number is O(n). Further, it is shown that for every integer m satisfying ⌊n^{2}/4⌋ < m ≤ \binom{n}{2} there exists no unit graph, while for each m such that n − 1 ≤ m ≤ ⌊n^{2}/4⌋ there exists at least one unit graph. Methods of proof are constructive.

1 INTRODUCTION

Sum graphs (defined in the Abstract) were introduced by Harary [Har88,Har89]. Hao [Hao89] showed that a graph of order n is a sum graph if and only if its size m ≤ (\binom{n}{2} − ⌊n/2⌋)/2; for a given graph G, he also established a lower bound on σ(G) in terms of the degree sequence of G. Gould and Rödl [GR89] derived complex upper and lower bounds on σ(G), expressed in terms of the order n and size m of G. In particular, their results show that there exist classes G of graphs such that over all G ∈ G, σ(G) ∈ Ω(n^{2}). However, they provide no method for the construction of such graphs, and the available constructive results all relate to special graphs G of small sum number; that is, such that σ(G) ∈ O(n). In particular, Ellingham [E89] has shown that for every non-trivial tree T, σ(T) = 1; Bergstrand et al. [BHHJKW89] that for every complete graph K_{n}, n ≥ 4, σ(K_{n}) = 2n − 3; Hartsfield and Smyth [HS89] that for every complete bipartite graph K_{p,q}, 2 ≤ p ≤ q, σ(K_{p,q}) = ⌈(3p + q − 3)/2⌉.

In this paper new results for graphs of small sum number are established; these results make some progress toward resolving an open problem posed by Harary [Har88]: the characterization of unit graphs.

Typeset by AMS-TEX

Section 2 uses methods similar to those of Gould and Rödl, but which are however constructive, to show that there exists a connected graph G of given order n and size m (n − 1 ≤ m < \binom{n}{2} − 1) such that σ(G) < σ(K_{n}) = 2n − 3. In Section 3 unit graphs of order n are considered. It is shown that for m > ⌊n^{2}/4⌋ no unit graph exists, while for every integer m satisfying n − 1 ≤ m ≤ ⌊n^{2}/4⌋, there exists a unit graph G of order n and size m.

Generally, in order to simplify notation, and where no ambiguity results, vertices of sum graphs will be referenced by their label under L.

2 CONSTRUCTING GRAPHS OF SMALL SUM NUMBER

In this section we show how to construct connected graphs G of given order n and size m for which σ(G) ∈ O(n).

For a sum graph G_{r} = (V, E), denote by {v_{1}, v_{2}, ..., v_{r}} the labels of the vertices of \overline{K}_{r}, where v_{1} < v_{2} < ... < v_{r}. For each v_{j}, 1 ≤ j ≤ r, let μ_{j} denote the number of edges (x, y) ∈ E such that x + y = v_{j}. Then μ_{j} is called the multiplicity of v_{j}. Now consider the special case in which G_{r} = K_{n} ∪ \overline{K}_{2n−3}, for some integer n ≥ 4. Then, as shown in [BHHJKW89], a correct labelling of G_{r} is achieved by assigning labels to the vertices of K_{n} as follows:

x_{i} = 4i − 3, 1 ≤ i ≤ n.

Hence the corresponding labels v_{j} of \overline{K}_{2n−3} are v_{j} = 4j + 2, 1 ≤ j ≤ 2n − 3.

Let us call this the standard labelling of K_{n} ∪ \overline{K}_{2n−3}. It is then straightforward to establish the following result:

Lemma 2.1 For every integer n ≥ 4, and for every positive integer j ≤ n − 1, the

standard labelling of K_{n} ∪ \overline{K}_{2n−3} yields multiplicities

μ_{j} = μ_{2n−j−2} = ⌈j/2⌉. □

It is worth noting that in fact the result of Lemma 2.1 holds for any correct labelling of K_{n} ∪ \overline{K}_{2n−3} [AHS90]. Multiplicity patterns for the first few values of n are shown in Table 2.1.

Multiplicities of \overline{K}_{2n−3}, 4 ≤ n ≤ 8
n  μ_{j}, 1 ≤ j ≤ 2n − 3
4  {1, 1, 2, 1, 1}
5  {1, 1, 2, 2, 2, 1, 1}
6  {1, 1, 2, 2, 3, 2, 2, 1, 1}
7  {1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1}
8  {1, 1, 2, 2, 3, 3, 4, 3, 3, 2, 2, 1, 1}

Table 2.1

Observe that if a vertex labelled v_{j} is removed from \overline{K}_{2n−3}, and if at the same time every edge (x, y) for which x + y = v_{j} is removed from K_{n}, the resulting graph (a subgraph of K_{n} ∪ \overline{K}_{2n−3}) will still be a sum graph. This process (removal of a single vertex v_{j} and all corresponding edges) applied to an arbitrary sum graph G_{r} = (V, E) is called a reduction and written

ϕ_{j} : G_{r} → G_{r−1},

where G_{r−1} = (V − {v_{j}}, E′) and |E′| = |E| − μ_{j}. We shall show that for every nonnegative integer m ≤ \binom{n−1}{2}, exactly m edges can be removed from the sum graph G_{2n−3}^{∗} = K_{n} ∪ \overline{K}_{2n−3} by a sequence of reductions, yielding a graph which consists of a single connected component together with isolated vertices, and which is therefore a sum graph of small sum number.

First consider the case m = \binom{n−1}{2}, so that the reduced graph contains \binom{n}{2} − \binom{n−1}{2} = n − 1 edges. Suppose that the vertices v_{1}, v_{2}, ..., v_{n−2} and v_{n+1}, v_{n+2}, ..., v_{2n−3} and their corresponding edges are removed, leaving only v_{n−1} and v_{n} from among the original isolated vertices. Since by Lemma 2.1,

μ_{n−1} + μ_{n} = ⌈\frac{n−1}{2}⌉ + ⌈\frac{n−2}{2}⌉ = n − 1,

the reduced graph G_{2}^{∗} certainly contains the prescribed number of edges. Further, let E_{n−1} and E_{n} denote the edges of G_{2}^{∗} corresponding to v_{n−1} and v_{n}, respectively; then both E_{n−1} and E_{n} are matchings of K_{n}, and in fact E_{n−1} is a maximum matching while |E_{n}| ≥ |E_{n−1}|−1. Since moreover E_{n−1} ∩ E_{n} = ϕ, it must be true that G_{2}^{∗} − {v_{n−1}, v_{n}} is connected, and we have

Lemma 2.2 Suppose that the sum graph G_{2n−3}^{∗} is repeatedly reduced by the reductions ϕ_{j} for every integer j = 1, 2, ..., n−2, n+1, n+2, ..., 2n−3. Then the reduced graph G_{2}^{∗} consists of a path P_{n} on n vertices together with two isolated vertices v_{n−1} and v_{n}. □

It follows from Lemma 2.2 that, provided v_{n−1} and v_{n} are not removed, any repeated reduction of G_{2n−3}^{∗} will always yield a single connected component together with a subset of the original set \overline{K}_{2n−3} of isolated vertices. We therefore consider a reduction strategy which leaves v_{n−1} and v_{n} intact.

In general, we seek reductions which transform the sum graph G_{2n−3}^{∗} into another sum graph G_{2n−3−k}^{∗} by removing k vertices and m edges. Each such transformation can be characterized by a set M of multiplicities removed from the original set {μ_{1}, μ_{2}, ..., μ_{2n−3}}. For such a set M, k = |M| is called the vertex remove and m = ∑_{μ∈M} μ is called the edge remove. For example, M = {1} would indicate the removal of k = 1 vertex and m = 1 corresponding edge; M = {1, 1, 1, 2} would indicate the removal of k = 4 vertices and m = 5 corresponding edges.

In order to uniquely identify the sets M of removed multiplicities, they are subscripted according to ”class” and by an ordinal within each class. For example, the sets corresponding to m = 1, 2, ..., 6 are written as follows:

M_{3,1} = {1};
M_{4,1} = {1, 1}, M_{4,2} = {1, 1, 1};
M_{5,1} = {1, 1, 1, 1}, M_{5,2} = {1, 1, 1, 1, 2}, M_{5,3} = {1, 1, 1, 1, 2}.

In general, the h^{th} class will contain h−2 sets M_{h,1}, M_{h,2}, ..., M_{h,h−2}, where for M_{h,h−2},

m_{h,h−2} = ∑_{μ∈M_{h,h−2}} μ = \binom{h−1}{2}

is the largest number of edges which can be removed from K_{h} without necessarily disconnecting it. We state a formal procedure for the iterative computation of the sets in each class based upon the sets in the previous class:

Procedure CONSTRUCT-MULTIPLICITY-SETS

Step 1 {Initialize.} M_{3,1} = {1}.
Step 2 {Iterate.} For h = 4, 5, ..., n do
Step 2.1 h′ ← ⌈h/2⌉ − 1.
Step 2.2 If h is even, then
for i = 1, 2, ..., h′ do
M_{h,i} ← M_{h−1,h′+i−1} ∪ {h′};
M_{h,h′+i} ← M_{h,i} ∪ {h′}.
Step 2.3 If h is odd, then
M_{h,h′} ← M_{h−1,h−3} ∪ {h′};
for i = 1, 2, ..., h′ − 1 do
M_{h,i} ← M_{h−1,h′+i−1} ∪ {h′ − 1};
M_{h,h′+i} ← M_{h,i} ∪ {h′}.

This procedure generates a sequence M of \binom{n−1}{2} sets M_{3,1}, M_{4,1}, M_{4,2}, M_{5,1}, ..., M_{n,1}, M_{n,2}, ..., M_{n,n−2}

in strictly increasing order of edge remove from m = 1 (M_{3,1}) to m = \binom{n−1}{2} (M_{n,n−2}). It is not difficult to see that every set of M is without loss of generality a subset of the multiplicities

{μ_{1}, μ_{2}, ..., μ_{n−2}, μ_{n+1}, μ_{n+2}, ..., μ_{2n−3}}.

Thus by Lemma 2.2 the sum graph associated with every element of M has a connected component of order n and a set of isolated vertices of cardinality less than 2n−3. Indeed, the exact number of isolated vertices may be computed for each element of M as a function of the number of removed edges:

Theorem 2.1 For every integer n ≥ 4 and every positive integer m ≤ \binom{n−1}{2}, let K_{n\m} denote the set of all graphs formed by removing exactly m edges from K_{n}. Then there exists G ∈ K_{n\m} such that σ(G) ≤ 2n − 1 − 2i − ⌊m/i⌋,

where i is the least integer such that m ≤ \binom{2i+1}{2}.

Proof The proof is by induction on n, based on the multiplicity sets generated by Procedure CONSTRUCT-MULTIPLICITY-SETS. The demonstration is laborious but straightforward, and is omitted. □

The condition on i in Theorem 2.1 may be expressed algebraically as i = ⌈(\sqrt{8m + 1} − 1)/4⌉.

Znám [Z91] has discovered an interesting alternative formulation of this result. Let i be the greatest integer such that m ≥ 4\binom{i}{2}; let j be the greatest non-negative integer such that m ≥ 4\binom{i}{2} + ij. Then there exists G ∈ K_{n\m} such that

σ(G) ≤ 2n + 1 − 4i − j.

3 UNIT GRAPHS

In this section we use the properties of unit graphs to improve upon Theorem 2.1 — to show, in fact, that for every integer n ≥ 2 and every integer m satisfying n − 1 ≤ m ≤ ⌊n^{2}/4⌋, there exists a unit graph of order n and size m.

Lemma 3.1 Let G = (V, E) denote a unit graph, and let G_{1} = G ∪ \overline{K}_{1} denote the corresponding sum graph. Suppose that G_{1} is correctly labelled. Then the vertex of V of greatest label u has degree one.

Proof Suppose u has degree at least two. Then u is adjacent to two distinct vertices which we suppose to be labelled x_{1} and x_{2}. Hence there must exist vertices of G_{1} labelled v_{1} = x_{1} + u > u and v_{2} = x_{2} + u > u. Since neither of these vertices can belong to V, they must both be isolated, contradicting the assumption that G is a unit graph. Hence u must have degree one. □

Lemma 3.2 Let d_{i}, 1 ≤ i ≤ n, denote the degrees of the vertices of a unit graph G, where d_{1} ≤ d_{2} ≤ ... ≤ d_{n}. Then d_{i} ≤ i.

Proof A consequence of a result of Hao [Hao89] that σ(G) > max_{1≤i≤n}(d_{i} − i). □

Lemma 3.3 There exists a unit graph of order n containing a clique on ν vertices if and only if ν ≤ ⌊n/2⌋ + 1.

Proof Since K_{ν} contains ν vertices of degree ν −1, it is easy to see that if the graph G of order n contains K_{ν}, then the vertex of (n − ν + 1)^{th} largest degree must have degree at least ν − 1. That is, in the symbolism of Lemma 3.2,

d_{n−ν+1} ≥ ν − 1.

If moreover ν > ⌊n/2⌋ + 1, then d_{n−ν+1} ≥ ν − 1 > n − ν + 1,

and Lemma 3.2 implies that G cannot be a unit graph.

To prove the converse, consider the sum graph G_{r} generated by vertices labelled consecutively 1, 2, ..., n + 1. The subgraph G ⊂ G_{1} induced by V = {1, 2, ..., n} is then in fact a unit graph, and G contains a clique of order ⌊n/2⌋ + 1. □

Theorem 3.1 No unit graph of order n has size m > ⌊n^{2}/4⌋.

Proof The unit graph on vertices V = {1, 2, ..., n}, together with isolated vertex n + 1, forms a sum graph of size

m = \binom{⌊n/2⌋+1}{2} + \binom{n−⌊n/2⌋}{2},

which after some manipulation becomes m = ⌊n^{2}/4⌋.

By Lemmas 3.2 and 3.3, there exists no unit graph of order n of larger size. □

Theorem 3.1 may also be deduced from Hao’s result, quoted in the Introduction, giving an upper bound on the size of a sum graph.

Theorem 3.2 For every integer n ≥ 2 and for every integer m satisfying n − 1 ≤ m ≤ ⌊n^{2}/4⌋, there exists a unit graph of order n and size m.

Proof Consider a sum graph G_{1} = (V, E) generated by V = {1, 2, ..., n + 1}. G_{1} contains a unit graph G^{(0)} of order n and size m = ⌊n^{2}/4⌋. We show first that by relabelling some of the vertices of V, unit graphs G^{(i)} of order n and size m − i can be constructed, for every positive integer i ≤ ⌊n/2⌋.

Let k = ⌊n/2⌋ and recall that G^{(0)} contains K_{k+1} as a subgraph. Hence separate V into subsets V_{1} = {1, 2, ..., k + 1} and V_{2} = {k + 2, k+3, ..., n+1}. Observe that the edges represented by any vertex label v ∈ V_{2} may be counted in two classes: m_{1} = m_{1}(v) edges of K_{k+1} and m_{2} = m_{2}(v) edges (x, y) which join x ∈ V_{1} to y ∈ V_{2}.

Suppose that k is even. Then labels v ∈ V_{2} correspond to these two classes of edge as shown in the following table (the last line occurs only in the case that n = 2k + 1):

v  m_{1}  m_{2}
k + 2  k/2  0
k + 3  k/2  1
k + 4  \frac{k}{2} − 1  2
.  .  .
.  .  .
.  .  .
2k  1  k − 2
2k + 1  1  k − 1
2k + 2  0  k

Observe that replacing V_{2} by another set V′_{2} = {v_{1}, v_{2}, ..., v_{n−k+1}} of distinct positive integers, where k + 1 < v_{1} < v_{2} < ... < v_{n−k}, will not affect the total number of edges counted by m_{2}, provided v_{n−k} − v_{1} ≤ k + 1. But the total number of edges counted by m_{1} can be reduced by exactly i if label k + 2i of V_{2} is replaced by 2k + 3, 1 ≤ i ≤ k/2, while all other labels are unchanged. Then this relabelling yields unit graphs G^{(i)} of order n and size m − i, for every positive integer i ≤ k/2. If now label k + 2 of V_{2} is replaced by 2k + 3, and if in addition label k + 2i + 1 is replaced by 2k + 4, then the total number of edges counted by m_{1} will be reduced by i + k/2, where 1 ≤ i ≤ k/2. We see then that unit graphs G_{(i)} of order n and size m − i can be constructed for every positive integer i ≤ k = ⌊n/2⌋. But since

⌊n^{2}/4⌋ − ⌊(n − 1)^{2}/4⌋ = ⌊n/2⌋,

it follows that unit graphs of order n and size m can be formed, for every integer m satisfying

⌊(n − 1)^{2}/4⌋ ≤ m ≤ ⌊n^{2}/4⌋.

The same conclusion is reached, by an almost identical argument, when k is odd.

To complete the proof, observe now that by the above result a single vertex and a path of length one can be added to a unit graph of order n − 1 and size

⌊(n − 2)^{2}/4⌋ ≤ m ≤ ⌊(n − 1)^{2}/4⌋,

thus yielding a unit graph of order n and size m + 1. More generally, s ≥ n − 4 vertices and a path of length s can be added to a unit graph of order n − s and size m satisfying

⌊(n − s − 1)^{2}/4⌋ ≤ m ≤ ⌊(n − s)^{2}/4⌋,

thus yielding a unit graph of order n and size m+s. If we consider consecutive values s = 1, 2, ..., n − 4 and observe that for s = n − 3,

n − 1 = ⌊(n − s)^{2}/4⌋ + (n − s),

if follows that unit graphs of order n and every size m satisfying n − 1 ≤ m ≤ ⌊n^{2}/4⌋

can be constructed, as required. □

It should be noted that Lemma 3.2 and Theorem 3.2 give rise to no converse. That is, there exist graphs whose degree sequence satisfies the conditions of Lemma 3.2 and whose size satisfies the condition of Theorem 3.2, but which are not unit graphs. An example is the star on six vertices with three additional edges joining four of the points of the star: V = {v_{1}, v_{2}, ..., v_{6}} and E = {v_{1}v_{i}, 2 ≤ i ≤ 6; v_{2}v_{3}, v_{3}v_{4}, v_{4}v_{5}}.

REFERENCES

[AHS90] N. Achuthan, N. Hartsfield, W. F. Smyth, work in progress.

[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.

[Har89] F. Harary, Sum graphs: some open questions, presentation at the Second International Conference on Graph Theory, Combinatorics, Algorithms & Applications.

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

[Z91] S. Znám, private communication.

ACKNOWLEDGEMENT

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