On regular graphs with \v{S}olt\'es vertices

MaRDI QIDQ6430372zbMATH OpenFDO

Authors Nino Bašić, Martin Knor, Riste Škrekovski

Publication date 21 March 2023

Mathematics Subject Classification ID

Distance in graphs (05C12) Applications of graph theory (05C90) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: Let $W(G)$ be the Wiener index of a graph $G$. We say that a vertex $vinV(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}oltes 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. We describe a construction that gives rise to an infinite family of cubic $2$-connected graphs with two 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 $frac13$-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.

This page was built for publication: On regular graphs with \v{S}olt\'es vertices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6430372)