Every Tree is an Integral Sum Graph

Abstract

A finite simple graph G is called an integral sum graph (respectively, sum graph) if there is a bijection f from the vertices of G to a set of integers S (respectively, a set of positive integers S) such that uv is an edge of G if and only if f (u)+f (v) ∈ S. In 1999, Liaw et al (Ars Comb., Vol.54, 259-268) posed the conjecture that every tree is an integral sum graph. In this note, we prove that all trees are integral sum graphs. Further, we prove that every bipartite graph is an induced subgraph of a sum graph G with sum number σ(G) = 1.