On the domination number of the product of two cycles. (English) Zbl 1212.05192

El-Zahar, Mohamed H.; Shaheen, Ramy S.

Ars Comb. 84, 51-64 (2007).

Summary: Let \(G=(V,E)\) be a graph. A subset \(D\subseteq V\) is called a dominating set for \(G\) if for every \(v\in V-D\), \(v\) is adjacent to some vertex in \(D\). The domination number \(\gamma (G)\) is equal to \(\min \{| D| \:D\text{ is a dominating set of }G\}\).
In this paper we calculate the domination numbers \(\gamma (C_m\times C_n)\) of the product of two cycles \(C_m\) and \(C_n\) of lengths \(m\) and \(n\) for \(m=5\) and \(n\equiv 3\!\pmod 5\), also for \(m=6,7\) and arbitrary \(n\).

MSC:

05C69

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Keywords:

domination; dominating sets; graph products; cycles