Bounds on the Size of the Minimum Dominating Sets of Some Cylindrical Grid Graphs

Abstract EN

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 we propose methods to find the domination numbers of graphs of the form Pm □ Cn with n≥3 and m=5 and propose tight bounds on domination numbers of the graphs P6 □ Cn, n≥3.

Moreover, we provide rough bounds on domination numbers of the graphs Pm □ Cn, n≥3 and m≥7.

We also point out how domination numbers and minimum dominating sets are useful for wireless sensor networks.