  Let $W(G)$ be the Wiener index of a graph $G$. We say that a vertex $v \in
V(G)$ is a \v{S}olt\'es vertex in $G$ if $W(G - v) = W(G)$, i.e. the Wiener
index does not change if the vertex $v$ is removed. In 1991, \v{S}olt\'es posed
the problem of identifying all connected graphs $G$ with the property that all
vertices of $G$ are \v{S}olt\'es vertices. The only such graph known to this
day is $C_{11}$. As the original problem appears to be too challenging, several
relaxations were studied: one may look for graphs with at least $k$
\v{S}olt\'es vertices; or one may look for $\alpha$-\v{S}olt\'es graphs, i.e.
graphs where the ratio between the number of \v{S}olt\'es vertices and the
order of the graph is at least $\alpha$. Note that the original problem is, in
fact, to find all $1$-\v{S}olt\'es graphs. We intuitively believe that every
$1$-\v{S}olt\'es graph has to be regular and has to possess a high degree of
symmetry. Therefore, we are interested in regular graphs that contain one or
more \v{S}olt\'es vertices. In this paper, we present several partial results.
For every $r\ge 1$ we describe a construction of an infinite family of cubic
$2$-connected graphs with at least $2^r$ \v{S}olt\'es vertices. Moreover, we
report that a computer search on publicly available collections of
vertex-transitive graphs did not reveal any $1$-\v{S}olt\'es graph. We are only
able to provide examples of large $\frac{1}{3}$-\v{S}olt\'es graphs that are
obtained by truncating certain cubic vertex-transitive graphs. This leads us to
believe that no $1$-\v{S}olt\'es graph other than $C_{11}$ exists.
