Some new formulae on Δ–optimum exclusive sum labeling of certain trees

Abstract

All sum graphs are disconnected. The notions of sum labeling and sum graphs were introduced by Harary [1] and later extended to include all integers [2]. A mapping L is called a sum labeling a graph H(V (H), E(H)) if it is an injection from V(H) to a set of positive integers such that xy ∈E(H) if and only if there exists a vertex w ∈V(H) such that L(w)=L(x) + L(y). In this case w is called a working vertex. We call L as an exclusive sum labeling of a graph G if it is sum labeling of for some non negative integer r and G contains no working vertex. In general, a graph G will require some isolated vertices to be labeled exclusively. The least possible number of such isolated vertices is called exclusive sum number of G, denoted by ∈(G). An exclusive sum labeling of a graph G is said to be optimum if it labels G exclusively by using ∈(G) isolated vertices. In case ∈(G)=Δ(G), where D(G) denotes the maximum degree of vertices in G, the labeling is called Δ- optimum exclusive sum labeling. In this paper we developed some new formulae to find Δ- optimum exclusive sum labeling of certain trees.

Keywords:

• Exclusive sum graph
• Exclusive sum number
• Exclusive sum labeling
• Paths
• Stars
• Double stars or Bistars
• Combs