2019/09/04 by Abraham Glasser, Glasser, Abraham, Bonnie Jacob +5 · 1 citation
Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Optimal Power Flow Distribution #Power System Optimization and Stability #Smart Grid Security and Resilience
paper · pdf · doi:10.48550/arxiv.1909.02057
openalex publication_date 2019/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a simple graph with vertex set V and edge set E, and let S ⊆ V. The open neighborhood of v ∈ V, N(v), is the set of vertices adjacent to v; the closed neighborhood is given by N[v] = N(v) ∪ \v\. The open neighborhood of S, N(S), is the union of the open neighborhoods of vertices in S, and the closed neighborhood of S is N[S] = S ∪ N(S). The sets Pi(S), i ≥ 0, of vertices monitored by S at the i^ th step are given by P0(S) = N[S] and Pi+1(S) = Pi(S) \bigcup\ w : \ w \ = N[v] \backslash Pi(S) for some v ∈ Pi(S) \. If there exists j such that Pj(S) = V, then S is called a power dominating set, PDS, of G. We introduce and discuss the failed power domination number of a graph G, γp(G), the largest cardinality of a set that is not a PDS. We prove that γp(G) is NP-hard to compute, determine graphs in which every vertex is a PDS, and compare γp(G) to similar parameters.