×

Bounds on the number of isolates in sum graph labeling. (English) Zbl 0987.05084

Summary: 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 \(\sigma(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 \(\sigma(G)\leq|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|\geq 3\) and \(|E|\), the average of \(\sigma(G)\) is at least \(|E|- 3|V|(\log|V|)/[\log({|V|\choose 2})/|E|)]-|V|-1\). In other words, for most graphs, \(\sigma(G)\in \Omega(|E|)\).

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C35 Extremal problems in graph theory
Full Text: DOI