On the domination number of the \(m\times n\) toroidal grid graph. (English) Zbl 0976.05045

Summary: Let \(G= (V,E)\) be a graph. A subset \(D\) of \(V\) is called a dominating set for \(G\) if for every \(v\in V\) either \(v\in D\), or else \(v\) is adjacent to some vertex in \(D\). The domination number of \(G\), denoted by \(\gamma(G)\), is equal to the minimum cardinality of a dominating set of \(G\). In this paper we establish the domination numbers of the toroidal graphs \(C_m\times C_n\) of the product of two cycles \(C_m\) and \(C_n\) of length \(m\) and \(n\) for \(m= 10\) and arbitrary \(n\), and for \(m,n\equiv 0\pmod 5\).


05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C38 Paths and cycles