| Title: | On regular graphs with Šoltés vertices |
|---|
| Authors: | ID Bašić, Nino (Author)
ID Knor, Martin (Author)
ID Škrekovski, Riste (Author) |
|---|
| Files: |  AMC_Basic_Nino_2025.pdf (456,75 KB)
MD5: 5DE6048F8C858933B9E546F43B36D188
|
|---|
| Language: | English |
|---|
| Work type: | Unknown |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | ZUP - University of Primorska Press
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 10.03.2025 |
|---|
| Publisher: | Založba Univerze na Primorskem |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 20 str. |
|---|
| Numbering: | Vol. 25, no. 2, [article no.] P2.01 |
|---|
| PID: | 20.500.12556/RUP-21706  |
|---|
| UDC: | 519.17 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | 10.26493/1855-3974.3085.3ea |
|---|
| COBISS.SI-ID: | 232776195 |
|---|
| Publication date in RUP: | 10.09.2025 |
|---|
| Views: | 290 |
|---|
| Downloads: | 2 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
