Spiro's minimum Wiener index conjecture for signed trees

A signed graph is a graph whose edges are assigned positive or negative signs. For a signed graph (G,σ)(G,\sigma), let Wσ(G)W_\sigma(G) denote the sum of the signed distances over all unordered pairs of distinct vertices. Let PnP_n be the path on nn vertices, and let α\alpha be an alternating signing of PnP_n, meaning that adjacent edges have opposite signs. A tree is a connected graph with no cycles. Spiro's conjecture. Among all signed trees of order nn, the alternating path (Pn,α)(P_n,\alpha) has the minimum Wiener index.

The conjecture concerns the extremal signed Wiener index among trees with a fixed number of vertices. The paper disproves it by constructing an infinite family of counterexamples, proving that it is false whenever n30n\ge 30.

Sources & referencesView supporting material

Primary source

Songlin Guo, Wei Wang and Chuanming Wang, “Disproof of a conjecture on the minimum Wiener index of signed trees”, arXiv:2208.01984 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.