On Fragile Power Domination

Amanda Verga; Beth Bjorkman; Johnathan Koch; Sean English

REVIEW 1 major objections 6 minor 15 references

On Fragile Power Domination

T0 review · 1 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The expected number of observed vertices under fragile power domination is equal for two graphs exactly when, for every subset size k, the total observations over all k-subsets of the sensor set are equal; add-on gadgets can force most…

desk verdict Solid gadget-based toolkit and a correct characterization theorem for fragile power domination; the one scary asserted identity checks out, and the remaining issues are expositional typos. read the letter →

arxiv 2507.14620 v1 pith:X4SNCLZE submitted 2025-07-19 math.CO

Beth Bjorkman , Sean English , Johnathan Koch , Amanda Verga This is my paper · ORCID

classification math.CO MSC 05C69

keywords fragilepowerdominationexpectedvaluepolynomialphasormeasurementunitssensorfailurezeroforcinggraphgadgetscoefficientcontrol

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies the expected number of observed vertices in a power grid when each PMU fails independently with probability q. Its central theorem is a characterization: two graphs with sensor sets of the same size produce the same expected-value polynomial exactly when, for every subset size k, the total number of vertices observed by all k-subsets of sensors is the same in both graphs. The paper also constructs Ψ and Φ gadgets that, when attached to the sensor set, can force the coefficients of q^k for k at least 2 to any prescribed integer, while proving that the constant and linear coefficients are not freely controllable. It gives a necessary and sufficient condition for the expected polynomial to be linear, and it builds a graph family in which a minimum sensor set made of degree-3 vertices strictly outperforms any minimum set containing a high-degree vertex.

What carries the argument

The load-bearing object is the expected value polynomial E(G;S,q), expressed in the Bernstein-type basis {$q^{{s-k}}$(1-q)^k}; the coefficient of each basis vector is the sum of |Obs(G;W)| over all k-subsets of the sensor set, which makes polynomial equality equivalent to finitely many integer equalities. The coefficient-control machinery consists of two gadget families, the Ψ and Φ gadgets, affixed to sensor vertices by identifying a set of affix vertices; Lemma 2.1 gives the probability that a gadget's path head is observed, and choosing appended path lengths lets the proof set the coefficient of q^k to any integer for k at least 2. Forts play a supporting role in lower bounds, because a sensor must lie in a fort or its entrance for the fort to be observed.

What would settle it

Recompute identity (19) directly for small parameters, for example s=3, t=w=d=0, by enumerating every subset W of the sensor set S' in the gadget graph H and summing |Obs(H;W)|; the resulting polynomial should equal -$5q^{2}$-9q+14, and any mismatch would refute the gadget count on which Theorem 3.7 rests.

Watch

Extended reading notes

Core claim

The paper's central claim is that the fragile power domination expectation E(G;S,q), as a polynomial in q, is completely encoded in the quantities a_k = sum over k-subsets W of S of |Obs(G;W)|. Theorem 3.1 shows that E(G;S,q)=E(G';S',q) iff a_k=a'_k for every 1≤k≤s, because the polynomial is written in the basis {$q^{{s-k}}$(1-q)^k} and these sums are exactly the basis coefficients. From this, the paper derives a sharp linearity criterion (Theorem 3.3), proves the reverse direction of a conjectured degree bound for general ℓ (Theorem 3.6), and proves the forward direction in the quadratic case when the linear coefficient is sufficiently negative (Theorem 3.7). It also proves a monotonicity result: if every k-subset total for one placement is at least as large as the corresponding total for another, then the first placement is at least as good at every failure probability, and a constructed graph family shows that degree is not a reliable guide to placement quality.

Load-bearing premise

The proof that the quadratic case of the conjecture works for polynomials with a sufficiently negative linear term relies on the asserted gadget count in identity (19), which is stated as 'straightforward to verify' without displaying the derivation; if that count is wrong, the replacement-graph argument for that direction collapses.

Editorial extensions

If this is right

Two sensor placements of the same size give identical expected coverage at every failure probability if and only if their k-subset observation totals agree for all k, so equality of networks can be decided by a finite integer comparison.
Attaching Ψ and Φ gadgets to a network can force all coefficients of q^k with k≥2 to arbitrary integer values, while the constant term stays at |Obs(G;S)| and the linear coefficient stays nonpositive.
A placement A is at least as good as a placement B at every q whenever each k-subset total of A is at least the corresponding total of B, and strictly better when some total is strictly larger.
The necessary-and-sufficient linearity condition (11) shows that linear expected coverage is equivalent to every k-subset total being exactly the binomial multiple of the sum over single sensors, generalizing the earlier sufficient condition of [4].
In the constructed graph family, minimum power dominating sets of degree-3 vertices are strictly better under fragile power domination than minimum sets containing high-degree clique vertices, so the low-degree avoidance heuristic is not valid in this random-failure setting.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The subset-sum characterization suggests a canonical numerical signature for expected coverage: the vector of the s quantities Σ_{W∈C(S,k)}|Obs(G;W)|. Comparing signatures is finite and could be automated, though computing all |Obs(G;W)| for large s is computationally expensive and may require new algorithms.
The gadget construction shows that expected-value polynomials are extremely flexible; one could design graphs whose expected coverage matches a target polynomial on [0,1], which in principle allows constructing test instances that expose weaknesses in PMU placement heuristics.
If Conjecture 3.4 is true, degree-ℓ expected polynomials would be determined by only ℓ integer parameters, so equality and dominance questions would collapse to small linear-algebra comparisons; the partial Theorem 3.7 is evidence that the conjecture holds at least for quadratics with a large negative linear coefficient.
The counterexample to the high-degree heuristic suggests a testable refinement: on random or structured grids, compare placements chosen by maximum degree versus placements chosen by maximum single-sensor observed set size, and check which achieves better expected coverage at intermediate failure probabilities.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should read this one. It is a genuine advance in the fragile power domination line, not just a re-coordinatization of earlier work. The new things: the Ψ/Φ gadget constructions that give coefficient-level control of the expected value polynomial (Theorem 2.3), the Bernstein-basis characterization of when two networks have identical expectation (Theorem 3.1), the concrete counterexample to the converse of the earlier linearity condition from [4], and the necessary-and-sufficient linearity characterization (Theorem 3.3). Section 4's comparison of sensor placements and the high-degree heuristic counterexample are also worth a look.

What the paper does well: the proofs are mostly complete and the gadget probability computations in Lemma 2.1 are careful and correct. Theorem 3.1 is a clean reduction of polynomial equality to finitely many integer conditions, and it genuinely makes the later arguments work. The example in Figure 3 is well chosen.

The one spot that made me nervous is identity (19) in the proof of Theorem 3.7, where the expected value of the replacement graph H is asserted as "straightforward to verify" without derivation. The reader flagged this as load-bearing. I sat down and computed it: the count is correct. A single surviving sensor at v0 observes w+9 vertices, two surviving sensors observe all 13+t+w vertices, and adding K_{d+1} and the s−3 isolated vertices reproduces exactly the claimed quadratic. So the concern does not land. That said, the authors should still add a short derivation; a referee cannot be expected to take an unproven count on faith for a theorem that uses it essentially.

The other issues are genuinely minor. In the proof of Theorem 3.3, the notation K_{s−1} is ambiguous: the argument only works if it means the empty graph, which the appendix does define but the body does not say. In the proof of Proposition 4.2, the displayed inequality has a sign error: the correct bound is λk(S) − λk(A) ≥ ℓ − (s choose k)2s^2, not the reverse. The conclusion still follows once you fix the sign, and it does not affect the theorem statement. Similarly, in Theorem 3.7's proof, the component label K_d should be K_{d+1}.

Central argument holds up. The partial forward direction of Conjecture 3.4 is honestly labeled, and the restriction to large negative linear coefficient is reasonable given Proposition 2.4. No circularity, no fitted parameters, no invented entities.

Who is this for? Anyone working on power domination, zero forcing, or probabilistic graph searching. It deserves a serious referee; the authors are pointed at the right open questions and the machinery is reusable. I would engage with it, and with a request for the short derivation of (19) plus the typo fixes, I would be comfortable accepting it.

Referee Report

1 major / 6 minor

Summary. The paper studies fragile power domination, where each PMU fails independently with probability q, and analyzes the expected number of observed vertices E(G;S,q). The main results are: a Bernstein-basis characterization of when two graphs with sensor sets of equal size have the same expected value polynomial (Theorem 3.1); a necessary and sufficient condition for E(G;S,q) to be linear (Theorem 3.3); partial progress on a conjecture characterizing polynomials of degree at most ℓ (Theorem 3.6 and Theorem 3.7); and a construction showing that minimum power dominating sets using only degree-3 vertices can be strictly better, in the fragile-power-domination sense, than sets containing a high-degree vertex (Section 4). Section 2 develops Ψ and Φ gadgets intended to control individual coefficients of the expected value polynomial.

Significance. The characterization in Theorem 3.1 is elegant and useful: it reduces polynomial equality to finitely many integer conditions, and it underpins the comparison machinery in Section 4. Theorem 3.3 gives a clean linearity criterion. The Section 4 counterexample to the high-degree heuristic is explicit and appears convincing. If the coefficient-control machinery of Section 2 were fully rigorous, it would be a valuable engineering tool for fragile power domination. However, the proof of Theorem 2.2 currently has a serious gap in the treatment of multiple overlapping gadgets, which affects one of the paper's advertised main results.

major comments (1)

[Section 2.2, Lemma 2.1 and Theorem 2.2] The proof of Theorem 2.2 assumes that each affixed gadget behaves independently, with the path-head observation probabilities given in Lemma 2.1, but Lemma 2.1 is only proved for a single affixed gadget. When several gadgets are affixed to overlapping sets A_i, a failed affix vertex can be observed by another gadget, which changes the observation probability of larger Φ gadgets. Concretely, take S={a,b,c,d}, f≡1, and affix Φ^2 at {a,c}, Φ^2 at {b,d}, and Φ^4 at {a,b,c,d}. If sensors a and b succeed and c and d fail, the two Φ^2 gadgets force c and d to be observed (in a Φ^2, a successful affix forces the cycle vertex y, which forces the failed affix). In the Φ^4 gadget, every B-vertex, i.e. every 3-subset of {a,b,c,d}, contains at least one of a or b, so all B-vertices are observed by domination; the B-vertex {a,c,d} then has all three of its A-neighbors observed, so it forces the connection vertex x, and x forces the path head. Thus the Φ^4 path head is observed despite only two of the four sensors in A succeeding, contradicting the formula in Lemma 2.1, which for a=4 requires at least three successes. The expressions for h_i(q) in equations (5)-(7) therefore do not account for cross-gadget contributions, and the coefficient-control argument in Theorem 2.2 is unsupported as written.

minor comments (6)

[Theorem 3.3 proof] The graph G' := K_{ℓ-s+1} ⊔ K_{s-1} should use the empty graph on s-1 vertices (overline{K}_{s-1}), not the complete graph; otherwise the graph has only two components and cannot contain one sensor in each of s components. The notation in the Appendix appears to have lost the overline.
[Theorem 3.7 proof] The component H2 is defined as K_d but the earlier construction uses K_{d+1}; the proof should read H2 = K_{d+1}, and K_{s-3} denotes the empty graph on s-3 vertices.
[Theorem 3.7, equation (19)] The identity E(H;S',q) = (t-w-5)q^2 - (s+2t+d+6)q + (s+t+w+d+11) is asserted as 'straightforward to verify'. The identity is correct, but the verification should be sketched, since it is load-bearing for the parameter choices that follow.
[Proposition 4.2 proof] The displayed inequality has a sign error: the correct bound is λ_k(S)-λ_k(A) ≥ ℓ - binom(s,k)2s^2, not binom(s,k)2s^2 - ℓ. With ℓ > s 2^{2s+1}, the corrected expression is positive, so the argument can be repaired, but the current text is inconsistent.
[Proposition 4.2, Case 1] The statement 'the only vertices v ∈ V(G) which have the property that L_i ⊆ Obs(G;v) are vertices in S' is too strong; a sensor placed inside a pendant path would observe that path. What is needed and true is that the specific vertex v_{1,2} ∈ K has no L_i contained in its observation set, which is what the case relies on.
[Theorem 3.7 statement] The polynomial is written as E(G;S,q) = ax^2 - bx + c but the variable should be q throughout.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all core theorems derive from definition (1) of the expected value polynomial, and the one underived computational claim (identity (19)) verifies by direct expansion.

full rationale

The derivation chain is self-contained from the defining expansion (1). Theorem 3.1 is an immediate consequence: writing E(G;S,q) = Σ_k a_k q^{s−k}(1−q)^k via (1) and invoking linear independence of the Bernstein basis (cited to [3], a standard external fact) gives the coefficient-sum characterization; nothing is fitted or imported. Theorem 3.3 proves both directions from (1) and Theorem 3.1 via the explicit comparison graph K_{ℓ−s+1} ⊔ K_{s−1}, whose expectation is computed from the same definition; the earlier sufficient condition [4, Prop. 3.2] is cited only to frame the counterexample and is not a premise of any proof. The gadget probabilities in Lemma 2.1 are proved in full, so Theorems 2.2–2.3 do not borrow their conclusions from the self-cited [4]. Conjecture 3.4's α-parameters are self-referential by definition, but Lemma 3.5 resolves well-definedness by induction and Theorem 3.6 uses only that lemma, so this is not circular. The one load-bearing assertion without a written derivation, identity (19) in Theorem 3.7 ('It is straightforward to verify'), checks out on direct computation: a single surviving sensor at v0 observes w+9 vertices (3 from 2P3, 2 from Ψ²_t, 4+w from Φ²_w), two survivors observe all 13+t+w vertices, giving E(H′;A,q) = 2q(1−q)(w+9) + (1−q)²(13+t+w) = (t−w−5)q² − (2t+8)q + (t+w+13); adding (d+1)(1−q) and (s−3)(1−q) reproduces (19) exactly, and the stated (t,w,d) choices match any quadratic with c = b−a. The remaining flagged items — the H₂ = K_d label in Theorem 3.7's component list (should be K_{d+1}) and the sign in Proposition 4.2's bound (the correct margin is ℓ − C(s,k)2s², which is still positive under ℓ > s2^{2s+1}) — are typographical and do not affect the arguments. Self-citations [4] and [5] supply the model (restated in full in Section 1.1) and background only; [6] is external work. No step reduces to its own input, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

This is a pure combinatorics paper. It introduces explicit graph gadgets (Ψ and Φ) as construction tools; these are fully specified combinatorial objects, not ungrounded postulated entities. There are no data-fitted free parameters: the gadget path lengths ℓ_i are existential construction choices made to satisfy coefficient equations, not empirical fits. The model assumptions (independent failure, the expected value polynomial) are taken from the prior fragile power domination literature and stated at the outset.

assumptions (5)

domain assumption Independent sensor failure with probability q, followed by domination and zero forcing steps
This is the fragile power domination model from [4]; all results are stated within this model.
standard math Equation (1): E(G;S,q) = Σ_{W⊆S} |Obs(G;W)| q^{|S\W|}(1-q)^{|W|}
The expectation over independent Bernoulli failures; this follows from linearity of expectation over the binomial distribution.
standard math Bernstein basis {q^{s-k}(1-q)^k} is a basis for polynomials of degree at most s
Used in Theorem 3.1 proof; standard linear algebra fact.
domain assumption A fort F requires a sensor in F or its entrance for vertices of F to be observed (Bozeman et al. [6])
Used in Proposition 4.2 to lower-bound the power domination number of G_s(ℓ).
standard math Binomial theorem
Used in Lemma 3.5 and Theorem 3.3 proofs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Fragile Power Domination." pith.science (2026). https://pith.science/paper/X4SNCLZE

@misc{pith2026250714620,
  author       = {Pith},
  title        = {Pith review of: On Fragile Power Domination},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X4SNCLZE}},
  note         = {Machine review of arXiv:2507.14620}
}

abstract

Power domination is a graph theoretic model which captures how phasor measurement units (PMUs) can be used to monitor a power grid. Fragile power domination takes into account the fact that PMUs may break or otherwise fail. In this model, each sensor fails independently with probability $q\in [0,1]$ and the surviving sensors monitor the grid according to classical power domination. We study the expected number of observed nodes under the fragile power domination model. We give a characterization for when two networks and initial sensor placements will behave the same according to this expectation. We also show how to control the behavior of this expectation by adding structure to a network.

Figures

Figures reproduced from arXiv: 2507.14620 by the authors.

**Figure 2.** Graphs G with E (G; S, q) = −3q 3 −4q+ 7 and G′ with E (G′ ; S, q) = (5−ℓ1 + 2ℓ2)q 3 + (−21+ 3ℓ1 − 3ℓ2 + ℓ3 − ℓ4)q 2 + (−16 − 3ℓ1 − 2ℓ3)q + (32 + ℓ1 + ℓ2 + ℓ3 + ℓ4). If we wanted to make e.g. E (G′ ; S, q) [q 3 ] = E (G′ ; S, q) [q 2 ] = 0, we could do so by setting ℓ1 = 5, ℓ2 = 0, ℓ3 = 6, and ℓ4 = 0. This choice of path lengths results in E (G′ ; S, q) = 43(1 − q) and the graph given in [PITH_FULL_IMAGE:figures/fu… view at source ↗

**Figure 3.** A graph G where E (G; {u, v, w}, q) is linear, but (10) is not satisfied for all X ⊆ {u, v, w}, showing that the converse of Theorem 3.2 is false. See [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: The graph H′ (t, w) := 2P3 ⊟A Ψ2 t ⊟A Φ 2 w with path head vertices of Ψ2 t and Φ2 w indicated in red, and A indicated in blue. Dashed edges represent the appended paths with t and w vertices. Proof. If (17) is satisfied for all 1 ≤ k ≤ s, then observe that E (G; S, …

**Figure 5.** Figure 5: The graph G4(5) from Construction 5 with F1 indicated in red. Thus, E (G; A, q) ⪯ E (G; B, q). Furthermore, for any q ∈ (0, 1) and any k ∈ [a], q a−k (1 − q) k ̸= 0, and thus as long as there exists some k ∈ [a] such that (23) is strict, (26) is also strict for q ∈ (0,…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[4]

Power domination with random sensor failure

B. Bjorkman, Z. Brennan, M. Flagg, and J. Koch. Power domination with random sensor failure. arXiv:2312.12259, 2023

work page Pith review arXiv 2023
[1]

Anderson and K

S. Anderson and K. Kuenzel. Power domination in cubic graphs and Cartesian products. Discrete Math., 345(11):Paper No. 113113, 10, 2022

work page 2022
[2]

Benson, D

K. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, and V. Vasilevska. Nordhaus-Gaddum problems for power domination. Discrete Appl. Math. , 251:103–113, 2018

work page 2018
[3]

D´ emonstration du th´ eor` eme de weierstrass fonde´ e sur le calcul des probabilit´ es

Sergei Bernstein. D´ emonstration du th´ eor` eme de weierstrass fonde´ e sur le calcul des probabilit´ es. Communications of the Kharkov Mathematical Society , 13:1–2, 1912

work page 1912
[5]

An Introduction to PMU-Defect-Robust Power Domination: Bounds, Bipartites, and Block Graphs

B. Bjorkman, E. Conrad, and M. Flagg. An introduction to pmu-defect-robust power domination: Bounds, bipartites, and block graphs. arXiv:2312.07377, 2023

work page Pith review arXiv 2023
[6]

Bozeman, B

C. Bozeman, B. Brimkov, C. Erickson, D. Ferrero, M. Flagg, and L. Hogben. Restricted power domi- nation and zero forcing problems. J. Comb. Optim. , 37(3):935–956, 2019

work page 2019
[7]

R. Brualdi. Introductory combinatorics. Pearson Prentice Hall, Upper Saddle River, NJ, fifth edition, 2010

work page 2010
[8]

Brueni and L

D. Brueni and L. Heath. The PMU placement problem. SIAM J. Discrete Math. , 19(3):744–761, 2005

work page 2005

Show all 15 references

[9]

Dorbec, M

P. Dorbec, M. Mollard, S. Klavˇ zar, and S. ˇ Spacapan. Power domination in product graphs. SIAM J. Discrete Math., 22(2):554–567, 2008

2008
[10]

Fast and I

C. Fast and I. Hicks. Effects of vertex degrees on the zero-forcing number and propagation time of a graph. Discrete Appl. Math. , 250:215–226, 2018

2018
[11]

Haynes, S

T. Haynes, S. Hedetniemi, S. Hedetniemi, and M. Henning. Domination in graphs applied to electric power networks. SIAM J. Discrete Math. , 15(4):519–529, 2002

2002
[12]

C. Lu, R. Mao, and B. Wang. Power domination in regular claw-free graphs. Discrete Appl. Math. , 284:401–415, 2020

2020
[13]

K. Pai, J. Chang, and Y. Wang. Restricted power domination and fault-tolerant power domination on grids. Discrete Appl. Math. , 158(10):1079–1089, 2010

2010
[14]

Prabhu, A

S. Prabhu, A. Arulmozhi, M. Henning, and M. Arulperumjothi. Power domination and resolving power domination of fractal cubic network. arXiv:2407.01935, 2024

2024 arXiv
[15]

Yang and B

W. Yang and B. Wu. Disproofs of three conjectures on the power domination of graphs. Discrete Appl. Math., 307:62–64, 2022. 20 A General Definitions and Notation For a given finite set A, the order of A, denoted |A|, is the number of elements in A. The natural numbers, denoted...

2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [4]

Power domination with random sensor failure

B. Bjorkman, Z. Brennan, M. Flagg, and J. Koch. Power domination with random sensor failure. arXiv:2312.12259, 2023

work page Pith review arXiv 2023

[2] [1]

Anderson and K

S. Anderson and K. Kuenzel. Power domination in cubic graphs and Cartesian products. Discrete Math., 345(11):Paper No. 113113, 10, 2022

work page 2022

[3] [2]

Benson, D

K. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, and V. Vasilevska. Nordhaus-Gaddum problems for power domination. Discrete Appl. Math. , 251:103–113, 2018

work page 2018

[4] [3]

D´ emonstration du th´ eor` eme de weierstrass fonde´ e sur le calcul des probabilit´ es

Sergei Bernstein. D´ emonstration du th´ eor` eme de weierstrass fonde´ e sur le calcul des probabilit´ es. Communications of the Kharkov Mathematical Society , 13:1–2, 1912

work page 1912

[5] [5]

An Introduction to PMU-Defect-Robust Power Domination: Bounds, Bipartites, and Block Graphs

B. Bjorkman, E. Conrad, and M. Flagg. An introduction to pmu-defect-robust power domination: Bounds, bipartites, and block graphs. arXiv:2312.07377, 2023

work page Pith review arXiv 2023

[6] [6]

Bozeman, B

C. Bozeman, B. Brimkov, C. Erickson, D. Ferrero, M. Flagg, and L. Hogben. Restricted power domi- nation and zero forcing problems. J. Comb. Optim. , 37(3):935–956, 2019

work page 2019

[7] [7]

R. Brualdi. Introductory combinatorics. Pearson Prentice Hall, Upper Saddle River, NJ, fifth edition, 2010

work page 2010

[8] [8]

Brueni and L

D. Brueni and L. Heath. The PMU placement problem. SIAM J. Discrete Math. , 19(3):744–761, 2005

work page 2005