Some results on the Wiener index related to the Šoltés problem of graphs (Q6180575): Difference between revisions

The Wiener index \(W(G)\) of a connected graph G is the sum of distances between its vertices. Given a graph \(G\), consider the number \[ R_{m}\left(G \right) =\frac{|\left\lbrace v\in V\left(G \right): W\left(G \right) -W\left(G-v \right)=m\in \mathbb{Z} \right\rbrace |}{|V\left(G \right) |}, \] where \(V\left(G \right) \) is the vertex set of \(G\) and \(G-v\) is the graph obtained from \(G\) by deleting the vertex \(v\). The authors in this paper show that there exist graphs \(G\) such that \(R_{m}\left(G \right) >\frac{1}{2}\), for every integer \(m \geq 0.\) Some of these graphs are regular graphs for odd \(m\geq 1.\) This result is related to the problem of finding graphs G with large \(R_{m}\left(G \right), \) posed by \textit{M. Akhmejanova} et al. [ibid. 325, 37--42 (2023; Zbl 1504.05059)].