On relaxed Šoltés's problem

Abstract

The Wiener index is a graph parameter originating from chemical graph theory. It is defined as the sum of the lengths of the shortest paths between all pairs of vertices in given graph.In 1991, Šoltés posed the following problem regarding Wiener index. Find all graphs such that its Wiener index is preserved upon removal of any vertex. The problem is far from being solved and to this day, only one such graph is known -- the cycle graph on 11 vertices.
In this paper we solve a relaxed version of the problem, proposed by Knor,Majstorović}, and Škrekovski. The problem is to find for a given $k$(infinitely many) graphs such that they have exactly $k$ vertices such that ifwe remove any one of them, the Wiener index stays the same. We call suchvertices \textit{good} vertices and we show that there are infinitely manycactus graphs with exactly $k$ cycles of length at least 7 that containexactly $2k$ good vertices and infinitely many cactus graphs with exactly $k$cycles of length $c \in \{5,6\}$ that contain exactly $k$ good vertices. Onthe other hand, we prove that $G$ has no good vertex if the length of thelongest cycle in $G$ is at most $4$.