Uniqueness conjecture for power domination reconfiguration graphs of complete bipartite graphs
Let be the complete bipartite graph with part sizes and , and let denote its power domination reconfiguration graph under token addition/removal reconfiguration. Uniqueness conjecture. is unique if and only if and . This is supported by the uniqueness results for with and , together with Sage computations for and ; the conjecture proposes the complete characterization, including the cases not covered by those results.
References
- Beth Bjorkman, Chassidy Bozeman, Daniela Ferrero, Mary Flagg, Cheryl Grood, Leslie Hogben, Bonnie Jacob and Carolyn Reinhart, “Power domination reconfiguration”, arXiv:2201.01798 (2022).
Progress summary
The conjecture remains open: several cases are known, but the proposed complete proof has not been independently assessed.
The conjecture, stated in the original power-domination reconfiguration work, predicts uniqueness for complete bipartite graphs exactly when neither part has size . The 2026 published article still presents this characterization as open.
Known results
- is unique for .
- is not unique for , via .
- is unique.
- Sage computations establish uniqueness for and ; the broader cases remain conjectural.
Community submission (unverified), November 7, 2026
A submitted proof argues that a new structural theorem, combined with the known reconfiguration reduction and small cases, proves the full characterization for all . This is an unverified claim, and no independent mathematical assessment was retrieved.
Current status (as of November 2026): The stated cases and computations are settled, but the complete characterization remains open because the submitted proof is unverified.
Solutions 1
Power-domination TAR uniqueness for complete bipartite graphs: PD^TAR(K_{s,t}) is unique if and only if s ≠ 2 and t ≠ 2See full solution
Result and scope. Bjorkman, Bozeman, Ferrero, Flagg, Grood, Hogben, Jacob and Reinhart, Power domination reconfiguration, arXiv:2201.01798, La Matematica 5 (2026): the uniqueness conjecture stated after Proposition p:K33 (still listed open in the Curtis-Flagg-Hogben survey arXiv:2406.05509v2, 2025). Proved: the new Core Theorem (for s,t >= 3, (s,t) != (3,3), K_{A,B} is the only graph on A ⊔ B with exactly its PD sets) via fort duality, pair forts, cross-degree rigidity isolating (3,3), two-sided completeness and independence; with the published TAR relabelling reduction (Bong-Carlson-Curtis-Haas-Hogben, Graphs Combin. 2023) formalized by a self-contained Hamming-isometry proof, and the source's small cases (K_2, K_{1,t}, K_{2,t} via K_{2,t}(e), K_{1,2} vs K_3, K_{3,3}) all formalized.
Complete proof: Power-domination TAR uniqueness for complete bipartite graphs: PD^TAR(K_{s,t}) is unique if and only if s ≠ 2 and t ≠ 2 · PDF.
The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.
This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.