On Balancedness of Some Graph Constructions

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^{\ast }:E(G)\to A$ defined by $f^{\ast }(xy)=f(x)\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^{\ast }}(i)=\text{card}\{e\in E(G):f^{\ast }(e)=i\}.$ A labeling $f$ of a graph $G$ is said to be friendly if $|v_f(0)–v_f(1)|\le 1.$If $|e_{f^{\ast }}(0)–e_{f^{\ast }}(1)|\le 1,$ then $G$ is said to be $\mathbf{\text{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.