On Balancedness of Some Graph Constructions

Suh-Ryung Kim1, Sin-Min Lee2, Ho Kuen Ng3
1Department of Mathematics Education Seoul National University Seoul 151-748 , Korea
2Department of Computer Science San Jose State University San Jose, California 95192 U.S.A.
3Department of Mathematics San Jose State University San Jose, California 95192 U.S.A.

Abstract

Let \( G \) be a graph with vertex set \( V(G) \) and edge set \( E(G) \). Let \( A = \{0, 1\} \). A labeling \( f: V(G) \to A \) induces a partial edge labeling \( f^*: E(G) \to A \) defined by \(f^*(xy) = f(x) \quad \text{if and only if } f(x) = f(y),\) for each edge \( xy \in E(G) \). For \( i \in A \), let \(
v_f(i) = \text{card}\{v \in V(G) : f(v) = i\}\) and \(e_{f^*}(i) = \text{card}\{e \in E(G) : f^*(e) = i\}.\) A labeling \( f \) of a graph \( G \) is said to be friendly if \(\lvert v_f(0) – v_f(1) \rvert \leq 1.\)If \(\lvert e_{f^*}(0) – e_{f^*}(1) \rvert \leq 1,\) then \( G \) is said to be \(\textbf{balanced}\). The balancedness of the Cartesian product and composition of graphs is studied in [19]. We provide some new families of balanced graphs using other constructions.