η(G) ≥ 2n for 2-connected graphs

Conjecture 5 · arXiv:1602.05184

arXiv Conjecture high confidence— first stated 2016-02-16

Authors: Marthe Bonamy, Martin Knor, Borut Lužar, Alexandre Pinlou, Riste Škrekovski

Status open medium confidence

Conjecture 5 from arXiv:1602.05184 strengthens the main result of the same paper (η(G) ≥ 2n−6 for 2-connected non-complete graphs) to η(G) ≥ 2n for n ≥ 10, excluding three specific graph families. A web search spanning 2016–2026 found no published paper that proves or disproves this stronger bound; the conjecture appears to remain open. Confidence is medium rather than high because the conjecture is now nine years old and absence of a resolution in the indexed literature is somewhat suspicious for a concretely stated bound.

Reviewer notes. The source paper itself proves the weaker bound η(G) ≥ 2n−6 (resolving a conjecture of Nadjafi-Arani, Khodashenas and Ashrafi) and published Conjecture 5 as a further challenge. A 2021 paper (arXiv:2108.04157) resolves different conjectures of Hriňáková, Knor and Škrekovski (2019) about variable Wiener/Szeged indices, and a 2023 survey (arXiv:2303.11405) covers Wiener index topics, but neither could be verified as addressing Conjecture 5 specifically. No resolution of the full η(G) ≥ 2n statement was found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $G$ be a 2-connected graph of order $n \geq 10$ not isomorphic to $K_n$, $K^2_n$, or $K^{n-2}_n$. Then $\eta(G) \geq 2n$.

Context

The authors note that while $\eta(K_n)=0$ and $\eta(K^2_n)=\eta(K^{n-2}_n)=2n-6$, computer search found only finitely many 2-connected graphs with $\eta(G)<2n$ and none on 10 or more vertices, motivating this stronger bound beyond the three exceptional families.

Source paper

On the difference between the Szeged and Wiener index
Marthe Bonamy, Martin Knor, Borut Lužar, Alexandre Pinlou, Riste Škrekovski · 2016-02-16
https://arxiv.org/abs/1602.05184 PDF source