← All problems

Uniqueness conjecture for power domination reconfiguration graphs of complete bipartite graphs

4 years old · traced to

Let Ks,tK_{s,t} be the complete bipartite graph with part sizes ss and tt, and let PDTAR(Ks,t)\mathscr{PD}^{TAR}(K_{s,t}) denote its power domination reconfiguration graph under token addition/removal reconfiguration. Uniqueness conjecture. PDTAR(Ks,t)\mathscr{PD}^{TAR}(K_{s,t}) is unique if and only if s≠2s\ne 2 and t≠2t\ne 2. This is supported by the uniqueness results for K1,tK_{1,t} with t≥3t\ge 3 and K3,3K_{3,3}, together with Sage computations for s∈{3,4}s\in\{3,4\} and t∈{3,4,5}t\in\{3,4,5\}; the conjecture proposes the complete characterization, including the cases not covered by those results.

References
  1. 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

Refreshed
Open

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 22. The 2026 published article still presents this characterization as open.

Known results

  • K1,tK_{1,t} is unique for t≥3t\ge 3.
  • K2,tK_{2,t} is not unique for t≥2t\ge 2, via PDTAR(K2,t)≅PDTAR(K2,t(e))\mathscr{PD}^{TAR}(K_{2,t})\cong\mathscr{PD}^{TAR}(K_{2,t}(e)).
  • K3,3K_{3,3} is unique.
  • Sage computations establish uniqueness for s∈{3,4}s\in\{3,4\} and t∈{3,4,5}t\in\{3,4,5\}; 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 s,ts,t. 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.

Sources

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 solutionHide 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.