On integral sum labeling of dense graphs

Abstract

A graph is said to be a \textit{sum graph} if there exists a set $S$ of positive integers as its vertex set with two vertices adjacent whenever their sum is in $S$. An integral sum graph is defined just as the sum graph, the difference being that the label set $S$ is a subset of $Z$ instead of set of positive integers. The sum number of a given graph $G$ is defined as the smallest number of isolated vertices which when added to $G$ results in a sum graph. The integral sum number of $G$ is analogous. In this paper, we mainly prove that any connected graph $G$ of order $n$ with at least three vertices of degree $(n-1)$ is not an integral sum graph. We characterise the integral sum graph $G$ of order $n$ having exactly two vertices of degree $(n-1)$ each and hence give an alternative proof for the existence theorem of sum graphs.