Power domination in graphs |
| |
Authors: | Min Zhao Liying Kang Gerard J Chang |
| |
Institution: | a Department of Mathematics, Shanghai University, Shanghai 20044, China b Department of Mathematics, National Taiwan University, Taipei 10617, Taiwan |
| |
Abstract: | The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 1998, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number γP(G) of a graph G is the minimum cardinality of a power dominating set of G. In this paper, we present upper bounds on the power domination number for a connected graph with at least three vertices and a connected claw-free cubic graph in terms of their order. The extremal graphs attaining the upper bounds are also characterized. |
| |
Keywords: | 05C69 |
本文献已被 ScienceDirect 等数据库收录! |
|