کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651028 | 1342516 | 2006 | 5 صفحه PDF | دانلود رایگان |
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 SS to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set SS (following a set of rules for power system monitoring). The power domination number γP(G)γP(G) of a graph GG is the minimum cardinality of a power dominating set of GG. 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.
Journal: Discrete Mathematics - Volume 306, Issue 15, 6 August 2006, Pages 1812–1816