On the balanced domination of graphs

Xu, Baogen ; Sun, Wanting ; Li, Shuchao ; Li, Chunhua

Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 933-946.

Résumé

Let $G=(V_G,E_G)$ be a graph and let $N_G[v]$ denote the closed neighbourhood of a vertex $v$ in $G$. A function $f\colon V_G\rightarrow \{-1,0,1\}$ is said to be a balanced dominating function (BDF) of $G$ if $\sum _{u\in N_G[v]}f(u)=0$ holds for each vertex $v\in V_G$. The balanced domination number of $G$, denoted by $\gamma _b(G)$, is defined as $$ \gamma _b(G)=\max \biggl \{\sum _{v\in V_G}f(v) \colon f\ \text {is a BDF of}\ G\biggr \}. $$ A graph $G$ is called $d$-balanced if $\gamma _b(G)=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 extremal graphs are characterized; several classes of $d$-balanced graphs are determined. Some open problems are proposed.

Détail

DOI : 10.21136/CMJ.2021.0055-20

Classification : 05C69, 05C70
Keywords: domination number; balanced dominating function; balanced domination number; $d$-balanced graph