PROBLEMS & CONJECTURES ON SUM GRAPHS

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

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

Sum graphs were introduced by Harary [Har88]. In 1989 Gould and Rödl [GR89], using non-constructive methods, showed that there exist infinite classes G of graphs such that, over G ∈ G, σ(G) ∈ Θ(n^{2}). In the same year 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) ≤ 2n − 3. Other constructions have been found for specific classes:

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

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

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

* Hartsfield and Smyth [HS92b] show that for wheels W_{n} of order n + 1 and size m = 2n, σ(W_{n}) ∈ Θ(m) (for all other classes G of graph whose sum number is known, G ∈ G implies that σ(G) ∈ o(m)).

Typeset by AMS-TEX

Thus to date constructions have mainly 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. In this paper we present a collection of problems and conjectures arising out of the work referenced above.

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.

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

[HS92b] N. Hartsfield, W. F. Smyth, A family of graphs of large sum number, submitted for publication.

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

ACKNOWLEDGEMENT

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