## Abstract

In this paper, we continue the study of power domination in graphs (see [T. W. Haynes et al., SIAM J. Discrete Math., 15 (2002), pp. 519-529; P. Dorbec et al., SIAM J. Discrete Math., 22 (2008), pp. 554-567; A. Aazami et al., SIAM J. Discrete Math., 23 (2009), pp. 1382-1399]). Power domination in graphs was birthed from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set following a set of rules (according to Kirschoff laws) for power system monitoring. The minimum cardinality of a power dominating set of a graph is its power domination number. We show that the power domination of a connected cubic graph on n vertices different from K3,3 is at most n/4 and this bound is tight. More generally, we show that for k ≥ 1, the k-power domination number of a connected (k+2)-regular graph on n vertices different from K_{k+2,k+2} is at most n/(k+3), where the 1-power domination number is the ordinary power domination number. We show that these bounds are tight.

Original language | English |
---|---|

Pages (from-to) | 1559-1574 |

Number of pages | 16 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 27 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2013 |

## Keywords

- Domination
- Electrical network monitoring
- Power domination
- Regular graphs

## ASJC Scopus subject areas

- General Mathematics