Catalog Home Page

A family of sparse graphs of large sum number

Hartsfield, N. and Smyth, W.F. (1995) A family of sparse graphs of large sum number. Discrete Mathematics, 141 (1-3). pp. 163-171.

PDF - Authors' Version
Download (217kB)
Link to Published Version:
*Subscription may be required


Given an integer r > 0, let Gr, = (Vr, 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 . Then | V | = n, |Vr| = n+r, and |E| = m. Let L:Vr → + denote a labelling of the vertices of Gr with distinct positive integers. Then Gr is said to be a sum graph if there exists a labelling L such that for every distinct vertex pair u and v of Vr, (u, v) ϵE if and only if there exists a vertex wϵVr 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 Gr is a sum graph. Gould and Rödl have shown that there exist infinite classes of graphs such that, over Gϵ, σ(G)ϵΘ(n2), but no such classes have been constructed. In fact, for all classes for which constructions have so far been found, σ(G)ϵo(m). In this paper we describe constructions which show that for wheels Wn of (sufficiently large) order n + 1 and size m = 2n, σ(Wn) = n/2 + 3 if n is even and n ⩽ σ (Wn) ⩽ n + 2 if n is odd. Hence for wheels σ (Wn) ϵΘ(m).

Publication Type: Journal Article
Publisher: Elsevier BV
Copyright: © 1995 Published by Elsevier B.V.
Item Control Page Item Control Page


Downloads per month over past year