BALANCED INDEX SETS OF GRAPHS AND SEMIGRAPHS

Abstract

Let G be a simple graph with vertex set V (G) and edge set E(G). Graph labeling is an assignment of integers to the vertices or the edges, or both, subject to certain conditions. For a graph G(V, E), a friendly labeling f : V (G) → {0, 1} is a binary mapping such that |vf (1) − vf (0)| ≤ 1, where vf (1) and vf (0) represents number of vertices labeled by 1 and 0 respectively. A partial edge labeling f ∗ of G is a labeling of edges such that, an edge uv ∈ E(G) is, f ∗(uv) = 0 if f (u) = f (v) = 0; f ∗(uv) = 1 if f (u) = f (v) = 1 and if f (u)̸ = f (v) then uv is not labeled by f ∗. A graph G is said to be balanced graph if it admits a vertex labeling f that satisfies the conditions, |vf (1) − vf (0)| ≤ 1 and |ef (1) − ef (0)| ≤ 1, where ef (0), ef (1) are the number of edges labeled with 0 and 1 respectively. The balanced index set of the graph G is defined as, {|ef (1) − ef (0)| : the vertex labeling f is friendly}. A semigraph is a generalization of graph. The concept of semigraph was introduced by E. Sampath Kumar. Frank Harrary has defined an edge as a 2-tuple (a, b) of vertices of a graph satisfying, two edges (a, b) and (a′, b′) are equal if and only if either a = a′ and b = b′ or a = b′ and b = a′. Using this notion, E. Sampath Kumar defined semigraph as a pair (V, X) where V is a non-empty set whose elements are called vertices of G and X is a set of n-tuples called edges of G of distinct vertices, for various n ≥ 2 satisfying the conditions: (i) Any two edges of G can have at most one vertex in common; and (ii) two edges (a1, a2, a3, ..., ap) and (b1, b2, b3, ..., bq ) are said to be equal if and only if the number of vertices in both edges must be equal, i.e p = q, and either ai = bi for 1 ≤ i ≤ p or ai = bp−i+1, 1 ≤ i ≤ p. In this article, balance index set of T (Pn), T (Wn), T (Km,n) and T (Sn) determined, and the balance index set of semigraph is introduced. Additionally, the balanced index set of semigraph Cn,m, Kn,m is determined.