Bounds on the number of isolates in sum graph labeling Original Research Article

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