The strengthened Szeged–Wiener lower bound for 2-connected graphs

Let GG be a 22-connected graph of order n10n\ge 10. Let KnK_n denote the complete graph, and let Kn2K_n^2 and Knn2K_n^{n-2} be the graphs obtained from Kn1K_{n-1} by adding one vertex adjacent to respectively 22 or n2n-2 of the original vertices. Define η(G)=Sz(G)W(G)\eta(G)=\operatorname{Sz}(G)-W(G). Strengthened Szeged–Wiener conjecture. If GG is not isomorphic to KnK_n, Kn2K_n^2, or Knn2K_n^{n-2}, then

η(G)2n.\eta(G)\ge 2n.

The conjecture is motivated by computer searches finding graphs with η(G)<2n\eta(G)<2n only up to order 99, with none on 1010 vertices. The source does not provide a proof or resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Martin Knor, Borut Lužar, Alexandre Pinlou and Riste Škrekovski, “On the difference between the Szeged and Wiener index”, arXiv:1602.05184 (2016).

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.