Sum Graphs from Trees

Abstract

A graph $G$ is a sum graph if there is a labeling $o$ of its vertices with distinct positive integers, so that for any two distinct vertices $u$ and $v$, $uv$ is an edge of $G$ if and only if $\sigma (u)+\sigma (v)=\sigma (w)$ for some other vertex $w$. Every sum graph has at least one isolated vertex (the vertex with the largest label). Harary has conjectured that any tree can be made into a sum graph with the addition of a single isolated vertex. We prove this conjecture.