Premium
Power domination in cylinders, tori, and generalized Petersen graphs
Author(s) -
Barrera Roberto,
Ferrero Daniela
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20413
Subject(s) - domination analysis , combinatorics , mathematics , cartesian product , vertex (graph theory) , cardinality (data modeling) , torus , upper and lower bounds , dominating set , graph , discrete mathematics , power (physics) , set (abstract data type) , computer science , physics , geometry , mathematical analysis , quantum mechanics , data mining , programming language
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