Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #97013 (December, 1997)

Bounds on Sum Number in Graphs
by Hiroshi Nagamochi, Mirka Miller and Slamin

A simple undirected graph $G$ is called a {\em sum graph} if there is a labeling $L$ of the vertices of $G$ into distinct positive integers such that any two vertices $u$ and $v$ of $G$ are adjacent if and only if there is a vertex $w$ with label $L(w)=L(u)+L(v)$. The sum number $\sigma(H)$ of a graph $H=(V,E)$ is the least integer $r$ such that graph $G$ consisting of $H$ and $r$ isolated vertices is a sum graph. It is clear that $\sigma(H)\leq |E|$. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that the average of $\sigma(H)$ over all graphs $H=(V,E)$ with fixed $|V|$ and $|E|$ is at least $|E|-3|V| \frac{\log |V|}{\log ({{|V|}\choose{2}}/|E|)}-|V|-1$. In other words, for most graphs, $\sigma(H)=\Omega(|E|)$.