On friendly index sets of k-galaxies

Abstract

Let G = (V, E) be a graph. A vertex labeling f : V → Z2 induces an edge labeling f * : E → Z2 defined by f * (xy) = f(x) + f(y), for each edge xy ∈ E. For i ∈ Z2, let vf(i) = ∣{v ∈ V : f(v) = i}∣ and ef(i) = ∣{e ∈ E : f * (e) = i}∣. We say that f is friendly if ∣vf(1) − vf(0)∣ ≤ 1. The friendly index set of G, denoted by FI(G), is defined as FI(G) = ∣ef(1) − ef(0)∣ : vertex labeling f is friendly. A k-galaxy is a disjoint union of k stars. In this paper, we establish the friendly index sets for various classes of k-galaxies.

Keywords

• friendly labeling, friendly index set, disjoint union of stars