A family of sparse graphs of large sum number

✍ Scribed by Nora Hartsfield; W.F. Smyth

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 440 KB
• Volume: 141
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0196-b

✦ Synopsis

Given an integer r ~>0, let G, =(V,, 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 K,. Then ]Vl=n, I V,l=n+r, and tEl=re. Let L://,--,7/+ denote a labelling of the vertices of G, with distinct positive integers. Then G, 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)EE if and only if there exists a vertex we V, 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, is a sum graph. Gould and R6dl have shown that there exist infinite classes ~q of graphs such that, over Ge~, a(G)eO(n2), but no such classes have been constructed. In fact, for all classes ff for which constructions have so far been found, e(G)eo(m). In this paper we describe constructions which show that for wheels W, of (sufficiently large) order n + 1 and size m=2n, a(W,)=n/2+3 if n is even and n<~a(W,)~n+2 if n is odd. Hence for wheels ~r(W,)~O(m).