Exclusive Sum Labelings of Trees

Abstract

The notions of sum labeling and sum graph were introduced by Harary in 1990. In a sum labeling, a vertex is called a working vertex if its label is equal to the sum of the labels of a pair of two distinct vertices.

A sum labeling of a graph $G$ is said to be $\text{exclusive}$ if it is a sum labeling of $G$ such that $G$ contains no working vertex. Any connected graph $G$ will require some additional isolated vertices in order to be labeled exclusively. The smallest number of such isolates is called the exclusive sum number of $G$; it is denoted by $ϵ(G)$. The number of isolates cannot be less than the maximum number of neighbors of any vertex in the graph, that is, at least equal to $\mathrm{\Delta }(G)$, the maximum vertex degree in $G$. If $ϵ(G)=\mathrm{\Delta }(G)$, then $G$ is said to be a $\mathrm{\Delta }$-$\text{optimum summable graph}$. An exclusive sum labeling of $G$ using $\mathrm{\Delta }(G)$ isolates is called a $\mathrm{\Delta }$-optimum exclusive sum labeling of $G$.

In this paper, we show that some families of trees are $\mathrm{\Delta }$-optimum summable graphs. However, this is not true for all trees, and we present an example of a tree that is not a $\mathrm{\Delta }$-optimum summable graph, giving rise to an open problem.