The Wiener index W(G) of a connected graph G is defined to be the sum of distances between all pairs of vertices in G. In 1991, Šoltés studied changes of the Wiener index caused by removing a single vertex. He posed the problem of finding all graphs G so that equality W(G)=W(G−v) holds for all their vertices v. The cycle with 11 vertices is still the only known graph with this property. In this paper we study a relaxed version of this problem and find graphs which Wiener index does not change when a particular vertex v is removed. We show that there is a unicyclic graph G on n vertices with W(G)=W(G−v) if and only if n≥9. Also, there is a unicyclic graph G with a cycle of length c for which W(G)=W(G−v) if and only if c≥5. Moreover, we show that every graph G is an induced subgraph of H such that W(H)=W(H−v). As our relaxed version is rich with solutions, it gives hope that Šoltes’s problem may have also some solutions distinct from C11.

Let D be a regular digraph with radius s. Then D is a radially Moore digraph if it has the maximum possible number of nodes and the diameter of D does not exceed s+1. We show that for each s and t there exists a regular radially Moors digraph of degree t with radius s. Moreover, we give an upper bound for the number of central nodes in radially Moore digraphs with degree two.