%A Bok, Jan
%A Jedličková, Nikola
%A Maxová, Jana
%D 2019
%T On relaxed Šoltés's problem
%K
%X 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 if we remove any one of them, the Wiener index stays the same. We call such vertices \textit{good} vertices and we show that there are infinitely many cactus graphs with exactly $k$ cycles of length at least 7 that contain exactly $2k$ good vertices and infinitely many cactus graphs with exactly $k$ cycles of length $c \in \{5,6\}$ that contain exactly $k$ good vertices. On the other hand, we prove that $G$ has no good vertex if the length of the longest cycle in $G$ is at most $4$.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1173
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 475-480%V 88
%N 3
%@ 0862-9544
%8 2019-07-26