Bounds on the number of isolates in sum graph labeling

Abstract

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)6|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 5xed |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|).