A family of sparse graphs of large sum number

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 Kr. Then | V | = n, |Vr| = n+r, and |E| = m. Let L:Vr → Z+ 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 G of graphs such that, over GϵG, σ(G)ϵΘ(n2), 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 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).