King's Total Domination Number on the Square of Side n

A set S 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 (G) is the minimum cardinality of a dominating set of G. In terms of a chess board problem, let Xn be the graph for chess pieceX on the square of side n. Thus, (Xn) is the domination number for chess piece X on the square of side n. In 1964, Yaglom and Yaglom established that (Kn) = n+2 3 2 : This extends to (Km;n) = m+2 3 n+2 3 for the rectangular board. A set S 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 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 n board. In this paper we note an error in one portion of their analysis and provide a correct general upperbound for t (Km;n) : Furthermore, we state improved upperbounds for t (Kn).