Advanced Search

Let $G=(V_G,E_G)$ be a graph and let $N_G\left[v\right]$ denote the closed neighbourhood of a vertex $v$ in $G$. A function $f:V_G\to \{-1,0,1\}$ is said to be a balanced dominating function (BDF) of $G$ if ${\sum }_{u\in N_G\left[v\right]}f\left(u\right)=0$ holds for each vertex $v\in V_G$. The balanced domination number of $G$, denoted by ${\gamma }_b\left(G\right)$, is defined as $${\gamma }_b\left(G\right)=max\left\{\sum _{v\in V_G}f\left(v\right):f\text{is}\text{a}\text{BDF}\text{of}G\right\}.$$ A graph $G$ is called $d$-balanced if ${\gamma }_b\left(G\right)=0$. The novel concept of balanced domination for graphs is introduced. Some upper bounds on the balanced domination number are established, in which one is the best possible bound and the rest are sharp, all the corresponding...