A Complete Characterization of Balanced Graphs

Abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. For a labeling $f:V(G)\to A=\{0,1\}$, define a partial edge labeling $f^{\ast }:E(G)\to A$ such that, for each edge $xy\in E(G)$,

$$f^{\ast }(xy)=f(x)\text{if and only if}f(x)=f(y).$$

For $i\in A$, let

$${\text{v}}_f(i)=|\{v\in V(G):f(v)=i\}|$$

and

$${\text{e}}_{f^{\ast }}(i)=|\{e\in E(G):f^{\ast }(e)=i\}|.$$

A labeling $f$ of a graph $G$ is said to be friendly if

$$|{\text{v}}_f(0)–{\text{v}}_f(1)|\le 1.$$

If a friendly labeling $f$ induces a partial labeling $f^{\ast }$ such that

$$|{\text{e}}_{f^{\ast }}(0)–{\text{e}}_{f^{\ast }}(1)|\le 1,$$

then $G$ is said to be balanced. In this paper, a necessary and sufficient condition for balanced graphs is established. Using this result, the balancedness of several families of graphs is also proven.