On regular graphs with Šoltés vertices

Let W (G) be the Wiener index of a graph G. We say that a vertex v is an element of V (G) is a & Scaron;olt & eacute;s 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, & Scaron;olt & eacute;s posed the problem of identifying all connected graphs G with the property that all vertices of G are & Scaron;olt & eacute;s vertices. The only such graph known to this day is C11. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least k & Scaron;oltes vertices; or one may look for alpha-& Scaron;olt & eacute;s graphs, i.e. graphs where the ratio between the number of & Scaron;olt & eacute;s vertices and the order of the graph is at least alpha. Note that the original problem is, in fact, to find all 1-& Scaron;olt & eacute;s graphs. We intuitively believe that every 1-& Scaron;olt & eacute;s 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 & Scaron;olt & eacute;s vertices. In this paper, we present several partial results. For every r >= 1 we describe a construction of an infinite family of cubic 2-connected graphs with at least 2r & Scaron;olt & eacute;s vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any 1-& Scaron;olt & eacute;s graph. We are only able to provide examples of large 13-& Scaron;olt & eacute;s graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no 1-& Scaron;olt & eacute;s graph other than C11 exists.