Optimum Sum Labeling of Finite Union of Sum Graphs

Helen Burhan1, Rahmi Rusin1, Kiki A. Sugeng1
1Department of Mathematics Faculty of Mathematics and Natural Science, University of Indonesia Depok 16424, Indonesia

Abstract

Let \( G = (V, E) \) be a simple, finite, and undirected graph. A sum labeling is a one-to-one mapping \( L \) from a set of vertices of \( G \) to a finite set of positive integers \( S \) such that if \( u \) and \( v \) are vertices of \( G \), then \( uv \) is an edge in \( G \) if and only if there is a vertex \( w \) in \( G \) and \( L(w) = L(u) + L(v) \). A graph \( G \) that has a sum labeling is called a sum graph. The minimal isolated vertex that is needed to make \( G \) a sum labeling is called the sum number of \( G \), denoted as \( \sigma(G) \). The sum number of a sum graph \( G \) is always greater than or equal to \( \delta(G) \), the minimum degree of \( G \). An optimum sum graph is a sum graph that has \( \sigma(G) = \delta(G) \). In this paper, we discuss sum numbers of finite unions of some families of optimum sum graphs, such as cycles and friendship graphs.

Keywords: Optimal sum labeling, cycles, complete graphs and friend- ship graphs.