King’s Total Domination Number on the Square of Side $n$

Abstract

A set $S\subseteq V$ is a dominating set of a graph $G=(V,E)$ if each vertex in $V$ is either in $S$ or is adjacent to a vertex in $S$. A vertex is said to dominate itself and all its neighbors. The domination number $\gamma (G)$ is the minimum cardinality of a dominating set of $G$. In terms of a chess board problem, let $X_n$ be the graph for chess piece $X$ on the square of side $n$. Thus, $\gamma (X_n)$ is the domination number for chess piece $X$ on the square of side $n$. In 1964, Yaglom and Yaglom established that $\gamma (K_n)={\lceil \frac{n+2}{2}\rceil }^2$. This extends to $\gamma (K_{m,n})=\lceil \frac{m+2}{3}\rceil \lceil \frac{n+2}{3}\rceil$ for the rectangular board. A set $S\subseteq V$ is a total dominating set of a graph $G=(V,E)$ if each vertex in $V$ is adjacent to a vertex in $S$. A vertex is said to dominate its neighbors but not itself. The total domination number ${\gamma }_t(G)$ is the minimum cardinality of a total dominating set of $G$. In 1995, Garnick and Nieuwejaar conducted an analysis of the total domination numbers for the king’s graph on the $m\times n$ board. In this paper, we note an error in one portion of their analysis and provide a correct general upper bound for ${\gamma }_t(K_{m,n})$. Furthermore, we state improved upper bounds for ${\gamma }_t(K_n)$.