Power domination in cylinders, tori, and generalized Petersen graphs

A set S of vertices is defined to be a power dominating set (PDS) of a graph G if every vertex and every edge in G can be monitored by the set S according to a set of rules for power system monitoring. The minimum cardinality of a PDS of G is its power domination number. In this article, we find upper bounds for the power domination number of some families of Cartesian products of graphs: the cylinders P n □ C m for integers n ≥ 2, m ≥ 3, and the tori C n □ C m for integers n , m ≥ 3. We apply similar techniques to present upper bounds for the power domination number of generalized Petersen graphs P ( m , k ). We prove those upper bounds provide the exact values of the power domination numbers if the integers m , n , and k satisfy some given relations. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 43–49 2011