Exclusive Sum Labeling of Graphs

Abstract

A graph $G(V,E)$ is called a sum graph if there is an injective labeling called sum labeling $L$ from $V$ to a set of distinct positive integers $S$ such that $xy\in E$ if and only if there is a vertex $w\in V$ such that $L(w)=L(x)+L(y)\in S$. In such a case, $w$ is called a working vertex. Every graph can be made into a sum graph by adding some isolated vertices, if necessary. The smallest number of isolated vertices that need to be added to a graph $H$ to obtain a sum graph is called the sum number of $H$; it is denoted by $\sigma (H)$. A sum labeling which realizes $H\cup \overline{K_{\sigma }(G)}$ as a sum graph is called an optimal sum labeling of $H$.

Sum graph labeling offers a new method for defining graphs and for storing them digitally. Traditionally, a graph is defined as a set of vertices and a set of edges, specified by pairs of vertices which are the endpoints of an edge. To record a graph on a computer, the edges are usually stored either in the form of an adjacency matrix or as a linked list. Using sum graph labeling, we only need to store the set of vertices, together with some additional isolates, if needed. While previously the edges in a graph were specified explicitly, using sum graphs, edges can be specified implicitly.

A sum labeling $L$ is called an exclusive sum labeling with respect to a subgraph $H$ of $G$ if $L$ is a sum labeling of $G$ where $H$ contains no working vertex. The exclusive sum number $ϵ(H)$ of a graph $H$ is the smallest number $r$ such that there exists an exclusive sum labeling $L$ which realizes $H\cup \overline{K_r}$ as a sum graph. A labeling $L$ is an optimal exclusive sum labeling of a graph $H$ if $L$ is a sum labeling of $H\cup K_{ϵ(H)}$ and $H$ contains no working vertex. While the exclusive sum number is never smaller than the corresponding sum number of a graph, labeling graphs exclusively has other desirable features which give greater scope for combining two or more labeled graphs.

In this paper, we introduce exclusive sum graph labeling and we construct optimal exclusive sum graph labeling for complete bipartite graphs, paths, and cycles. The paper concludes with a summary of known results in exclusive sum labeling and exclusive sum numbers for several classes of graphs.