Labelling Wheels for Minimum Sum Number

Abstract

A simple undirected graph $G$ is called a \emph{sum graph} if there exists a labelling $\lambda$ 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 $\lambda (w)=\lambda (u)+\lambda (v)$. It is obvious that every sum graph has at least one isolated vertex, namely the vertex with the largest label. The \emph{sum number} $\sigma (H)$ of a connected graph $H$ is the least number $r$ of isolated vertices ${\overline{K}}_r$ such that $G=H+{\overline{K}}_r$ is a sum graph.
It is clear that if $H$ is of size $m$, then $\sigma (H)\le m$. Recently, Hartsfield and Smyth showed that for wheels $W_n$ of order $n+1$ and size $m=2n$, $\sigma (W_n)\in \mathrm{\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\ge 4$, $\sigma (W_n)=n/2+2$, while for odd $n\ge 5$ we disprove a conjecture of Hartsfield and Smyth by showing that $\sigma (W_n)=n$. Labellings are given that achieve these minima.