2022/09/08 by Sarah E. Anderson, Anderson, Sarah E., Kirsti Kuenzel +3
Computer Science · #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2209.03930
Power domination is a two-step observation process that is used to monitor power networks and can be viewed as a combination of domination and zero forcing. Given a graph G, a subset S⊆ V(G) that can observe all vertices of G using this process is known as a power dominating set of G, and the power domination number of G, γP(G), is the minimum number of vertices in a power dominating set. We introduce a new partition on the vertices of a graph to provide a lower bound for the power domination number. We also consider the power domination number of the Cartesian product of two graphs, G \Box H, and show certain graphs satisfy a Vizing-like bound with regards to the power domination number. In particular, we prove that for any two trees T1 and T2, γP(T1)γP(T2) ≤ γP(T1 \Box T2).