A study on edge coloring and edge sum coloring of integral sum graphs

Abstract

Frank Harary introduced the concept of integral sum graph. A graph $G$ is an \emph{ integral sum graph} if its vertices can be labeled with distinct integers so that $e=uv$ is an edge of $G$ if and only if the sum of the labels on vertices $u$ and $v$ is also a label in $G.$ For any non-empty set of integers $S$, let $G^{+}(S)$ denote the integral sum graph on the set $S$. In $G^{+}(S)$, we define an \emph{edge-sum class} as the set of all edges each with same edge sum number and call $G^{+}(S)$ an \emph{edge sum color graph} if each edge-sum class is considered as an edge color class of $G^{+}(S)$. The number of distinct edge-sum classes of $G^{+}(S)$ is called its \emph{ edge sum chromatic number}. The main results of this paper are (i) the set of all edge-sum classes of an integral sum graph partitions its edge set; (ii) the edge chromatic number and the edge sum chromatic number are equal for the integral sum graphs $G_{0,s}$ and $S_n$, Star graph of order $n$, whereas it is not in the case of $G_{r,s}=G^{+}([r,s])$, $r<0<s$, $n,s\ge 2$, $n,r,s\in \mathbb{N}$. We also obtain an interesting integral sum labeling of Star graphs.