Improved Bounds on the Szeged-Wiener Gap and the BKLPS Conjecture

Abstract

Bonamy-Knor-Lužar-Pinlou-Škrekovski (2017) define $K_n^t$ to be the complete graph of $n-1$ vertices but with an extra vertex that's adjacent to $t$ vertices of the complete graph part. They propose a stronger conjecture which asserts that if $G$ is a finite simple $2$-connected graph of order $n\ge 10$ not isomorphic to $K_n$, $K_n^2$, nor $K_n^{n-2}$, then the Szeged-Wiener gap of $G$ is $\eta (G)\ge 2n$. We improve upon their work to tighten the bounds on the Szeged-Wiener gap, allowing us to prove this conjecture in the affirmative. Afterwards, we construct graphs attaining equality for each $n\ge 10$ and pose a problem for interested readers to determine a necessary and sufficient condition for equality.

16 pages