Some results on integral sum graphs

AbstractLet Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,v∈S,uv∈E if and only if u+v∈S. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let ⌈x⌉ denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(Kn−E(Kr)) for r⩾⌈2n/3⌉−1, (ii) obtain a lower bound for ζ(Kn−E(Kr)) when 2⩽r<⌈2n/3⌉−1 and n⩾5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(Kr,r) for r⩾2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of Kr,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211)