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|)$.