Some results on the Wiener index related to the Šoltés problem of graphs

Abstract

The Wiener index, $W(G)$, of a connected graph $G$ is the sum of distances between its vertices. In 2021, Akhmejanova et al. posed the problem of finding graphs $G$ with large $R_m(G)=|\{v\in V(G)|W(G)-W(G-v)=m\in \mathbb{Z}\}|/|V(G)|$. It is shown that there is a graph $G$ with $R_m(G)>1/2$ for any integer $m\ge 0$. In particular, there is a regular graph of even degree with this property for any odd $m\ge 1$. The proposed approach allows to construct new families of graphs $G$ with $R_0(G)\to 1/2$ when the order of $G$ increases.

9 pages, 3 tables, 7 figures