Labelling wheels for minimum sum number
Miller, M., Ryan, J., SLAMIN, . and Smyth, W.F. (1998) Labelling wheels for minimum sum number. Journal of Combinatorial Mathematics and Combinatorial Computing, 28 . pp. 289-297.
A simple undirected graph G is called a sum graph if there exists a labelling L 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 L(w) = L(u) +L(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.
|Publication Type:||Journal Article|
|Publisher:||Charles Babbage Research Centre|
|Item Control Page|
Downloads per month over past year