On regular graphs with Šoltés vertices - Bašić, Nino (Ars mathematica contemporanea, 2025)
Let ?$W(G)$? be the Wiener index of a graph ?$G$?. We say that a vertex ?$v \in V(G)$? is a Šolté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, Šoltés posed the problem of identifying all connected graphs ?$G$? with the property that all vertices of ?$G$? are Šoltés 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$? Šoltés vertices; or one may look for ?$α$?-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least ?$α$?. Note that the original problem is, in fact, to find all ?$1$?-Šoltés graphs. We intuitively believe that every ?$1$?-Šolté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 Šoltés 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$? Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any ?$1$?-Šoltés graph. We are only able to provide examples of large ?$\frac{1}{3}$?-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no ?$1$?-Šoltés graph other than ?$C_{11}$? exists.
Keywords: Cayley graph; cubic graphs; regular graphs; Šoltés problem; Šoltés vertex; Wiener index