On regular graphs with Šoltés vertices

Bašić, Nino (author), Knor, Martin (author), Škrekovski, Riste (author)

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 $\alpha$-Š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 $\alpha$. 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.

• Language: English
• Keywords: Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication version: Version of Record
• Publication date: 01.01.2025
• Year: 2025
• Number of pages: 20 str.
• Numbering: Vol. 25, no. 2, article no. P2.01
• PID: 20.500.12556/RUL-168564
• UDC: 519.17
• ISSN on article: 1855-3966
• DOI: 10.26493/1855-3974.3085.3ea
• COBISS.SI-ID: 232776195
• Publication date in RUL: 17.04.2025

Record is a part of a journal

• Title: Ars mathematica contemporanea
• Publisher: Društvo matematikov, fizikov in astronomov, Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
• ISSN: 1855-3966
• COBISS.SI-ID: 239049984

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.