Power domination in regular claw-free graphs

Changhong Lü, Rui Mao, Wang Bing

Power domination is a graph-theoretic model for the optimal placement of Phase Measurement Units (PMUs) in electrical power systems. While standard domination requires a sensor to be adjacent to a node to monitor it, power domination incorporates physical propagation rules based on Kirchhoff’s laws: if a monitored node has exactly one unobserved neighbor, that neighbor also becomes observed. This paper establishes new theoretical bounds for this problem in specific network topologies and introduces an efficient algorithmic solution for tree structures.

Theoretical Bounds and the Dorbec Conjecture

A central focus of the research is the power domination number ($\gamma_p(G)$) of connected 4-regular claw-free graphs. A graph is "claw-free" if it does not contain $K_{1,3}$ as an induced subgraph, a property common in many real-world network models like line graphs.

Previously, Dorbec et al. (2013) conjectured that for any $r$-regular graph, the power domination number is at most $n/(r+1)$. This paper disproves that conjecture for the $r=4$ case by proving a slightly higher sharp bound:

$$\gamma_p(G) \le \frac{n+1}{5}$$

This result indicates that the local "clumpiness" inherent in claw-free structures can limit the efficiency of the propagation rule compared to more general graph classes.

Structural Proof via Reductions

To prove the $(n+1)/5$ bound, the authors employ a proof-by-contradiction using a "minimal counterexample" approach. They identify a set of forbidden subgraphs (labeled $J_1$ through $J_{14}$) and demonstrate that if a graph contains such a structure, it can be reduced to a smaller graph without increasing the relative sensor requirement.

Figure 6: Operation 2 demonstrates how a specific subgraph J4 can be reduced to a simpler structure during the proof process.

By systematically eliminating these configurations, the authors narrow the possible architecture of a counterexample until it is shown to be impossible, thereby validating the bound.

Algorithmic Innovation for Weighted Trees

Beyond theoretical bounds, the paper addresses the Weighted Power Domination Problem in trees. In this variation, each node has an associated cost, and the goal is to minimize the total cost of sensors while maintaining full observability.

The authors developed Algorithm WPDT, a linear-time ($O(n)$) dynamic programming approach based on Wimer’s methodology. The algorithm categorizes subtrees into five distinct states based on the root's observation status and sensor placement. By defining transition rules between these states, the algorithm computes the global optimum in a single bottom-up pass from the leaves to the root.

Sharpness and Structural Examples

The bound $\frac{n+1}{5}$ is shown to be "sharp," meaning there exist specific graph families where this many sensors are strictly necessary. The paper identifies several base structures that characterize these extreme cases.

Figure 3: Examples of specific graph structures (I1 through I8) used to analyze the structural properties and sharpness of the power domination bound.

Conclusion and Future Directions

This work refines our understanding of sensor placement efficiency in regular networks. While the $O(n)$ algorithm provides an optimal solution for trees, future research may extend these techniques to graphs with low treewidth, which more closely resemble the cyclic nature of actual power grids. Additionally, generalizing the sharp bound for all $r$-regular claw-free graphs remains an open question in the field.

Summary updated

Abstract

In this paper, we first show that the power domination number of a connected $4$-regular claw-free graph on $n$ vertices is at most $\frac{n+1}{5}$, and the bound is sharp. The statement partly disprove the conjecture presented by Dorbec et al. in SIAM J. Discrete Math., 27:1559-1574, 2013. Then we present a dynamic programming style linear-time algorithm for weighted power domination problem in trees.
BibTeX
@article{lu2020power,
  author = {Changhong Lü and Rui Mao and Wang Bing},
  title = {{Power domination in regular claw-free graphs}},
  journal = {Discret. Appl. Math.},
  year = {2020},
  doi = {10.1016/j.dam.2020.03.055},
}
Figure