Labelling wheels for minimum sum number
Mirka Miller, Joe Ryan, Slamin Slamin, W.F. Smyth · Murdoch Research Repository (Murdoch University) · 1998
A simple undirected graph G is called a sum graph if there exists a labelling of the vertices of G into distinct positive integers such that any two distinct vertices u and v of G are adjacent if and only if there is a vertex w whose label (w) = (u) + (v). It is obvious that every sum graph has at least one isolated vertex, namely the vertex with the largest label. The sum number oe(H) of a connected graph H is the least number r of isolated vertices K r such that G = H+K r is a sum graph. It is clear that if H is of size m, then oe(H) m. Recently Hartsfield and Smyth showed that for wheels W n of order n+1 and size m = 2n, oe(W n ) 2 \\Theta(m); that is, that the sum number is of the same order of magnitude as the size of the graph. In this paper we refine these results to show that for even n 4, oe(W n ) = n=2+ 2, while for odd n 5 we disprove a conjecture of Hartsfield and Smyth by showing that oe(W n ) = n. Labellings are given that achieve these minima.