| Naslov: | On regular graphs with Šoltés vertices |
|---|
| Avtorji: | ID Bašić, Nino (Avtor)
ID Knor, Martin (Avtor)
ID Škrekovski, Riste (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (457,76 KB)
MD5: C122CCC75F1CA8729D5422D8EDD1DF59
 URL - Izvorni URL, za dostop obiščite https://amc-journal.eu/index.php/amc/article/view/3085
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
 RUDOLFOVO - Rudolfovo – Znanstveno in tehnološko središče Novo mesto
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.01.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 20 str. |
|---|
| Številčenje: | Vol. 25, no. 2, article no. P2.01 |
|---|
| PID: | 20.500.12556/DiRROS-22051  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1855-3966 |
|---|
| DOI: | 10.26493/1855-3974.3085.3ea |
|---|
| COBISS.SI-ID: | 232776195 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 17.04.2025 |
|---|
| Število ogledov: | 151 |
|---|
| Število prenosov: | 57 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
