The domination numbers of cylindrical grid graphs

摘要

Let γ(Pm □ Cn) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs Pm, the path of length m, m ⩾ 2 and the graph Cn, the cycle of length n, n ⩾ 3. In this paper, methods to find the domination numbers of graphs of the form Pm □ Cn with n ⩾ 3 and m = 2, 3 and 4 are proposed. Moreover, bounds on domination numbers of the graphs P5 □ Cn, n ⩾ 3 are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs.