TOPICS
Search

Spiro's Signed-Tree Conjecture


Spiro's signed-tree conjecture concerns the minimum signed Wiener index W_*(T) of a tree T, obtained by minimizing the signed index over all assignments of signs to its edges. Spiro (2022) proposed two bounds for a tree on n vertices. The lower bound is W_*(P_n), where P_n is the path graph and an alternating signing gives W_*(P_n)=|_n^2/4_|, with |_x_| denoting the floor function. The upper bound is the largest W_*(D) over n-vertex double stars, formed by joining the centers of two star graphs by an edge.

Guo et al. (2023) refuted the lower bound for every n>=30. Orden (2026) reports that the path graph is the unique minimizing underlying tree for 4<=n<=28. At n=29 it ties with exactly one other tree, with minimum 210. Claude agents developed a filter and exact search programs. Two separately written implementations shared part of the method and agreed on the results. The author released code and certificates, and the note is under journal review.

The upper bound is a separate open question. Orden (2026) reports finite checks through 28 vertices.


See also

Path Graph, Signed Graph, Tree, Wiener Index

Explore with Wolfram|Alpha

References

Guo, S.; Wang, W.; and Wang, C. "Disproof of a Conjecture on the Minimum Wiener Index of Signed Trees." Appl. Math. Comput. 439, 127577, 2023. https://doi.org/10.1016/j.amc.2022.127577.Orden, T. S. "Spiro's Conjecture on Signed Trees." 2026. https://doi.org/10.5281/zenodo.24095621.Spiro, S. "The Wiener Index of Signed Graphs." Appl. Math. Comput. 416, 126755, 2022. https://doi.org/10.1016/j.amc.2021.126755.

Cite this as:

Weisstein, Eric W. "Spiro's Signed-Tree Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SpirosSigned-TreeConjecture.html

Subject classifications