| Title: | On regular graphs with Šoltés vertices |
|---|
| Authors: | ID Bašić, Nino (Author)
ID Knor, Martin (Author)
ID Škrekovski, Riste (Author) |
|---|
| Files: |  PDF - Presentation file, download (457,76 KB)
MD5: C122CCC75F1CA8729D5422D8EDD1DF59
 URL - Source URL, visit https://amc-journal.eu/index.php/amc/article/view/3085
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
 RUDOLFOVO - Rudolfovo - Science and Technology Centre Novo Mesto
|
|---|
| 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 status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.01.2025 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | 20 str. |
|---|
| Numbering: | Vol. 25, no. 2, article no. P2.01 |
|---|
| PID: | 20.500.12556/DiRROS-22051  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1855-3966 |
|---|
| DOI: | 10.26493/1855-3974.3085.3ea |
|---|
| COBISS.SI-ID: | 232776195 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 17.04.2025 |
|---|
| Views: | 1024 |
|---|
| Downloads: | 281 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
