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.
*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|
|Copyright:||© 1995 Published by Elsevier B.V.|
|Item Control Page|
Downloads per month over past year