Critical cyclic patterns related to the domination number of the torus (Q864152)

The torus \(T_{m,n}\) is the Cartesian product \(C_m \times C_n\) of two chordless cycles. This paper deals with minimum dominating sets of \(T_{m,n}\) and their cardinalities, \(\gamma(T_{m,n})\). \textit{V. G. Vizing} [Vychisl. Sistemy, Novosibirsk 9, 30--43 (1963; Zbl 0194.25203)] conjectured \(\gamma(G \times H) \geq \gamma(G)\cdot\gamma(H)\) for all graphs \(G\) and \(H\). \textit{M. Livingston} and \textit{Q. F. Stout} [Congr.\ Numerantium 105, 116--128 (1994; Zbl 0842.68054)] gave an algorithm for computing \(\gamma(T_{m,n})\). Here, lower bounds on \(F(m) = \lim_{n \to \infty} \gamma(T_{m,n})/n\) are shown. In some cases these are tight and the patterns of minimum dominating sets are depicted.