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

Shaheen, Ramy S.

Congr. Numerantium 146, 187-200 (2000).

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\).

MSC:

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

Keywords:

domination number; dominating set; toroidal graphs; cycles