| Naslov: | On regular graphs with Šoltés vertices |
|---|
| Avtorji: | ID Bašić, Nino (Avtor)
ID Knor, Martin (Avtor)
ID Škrekovski, Riste (Avtor) |
|---|
| Datoteke: |  AMC_Basic_Nino_2025.pdf (456,75 KB)
MD5: 5DE6048F8C858933B9E546F43B36D188
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Neznano |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | 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 |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 10.03.2025 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 20 str. |
|---|
| Številčenje: | Vol. 25, no. 2, [article no.] P2.01 |
|---|
| PID: | 20.500.12556/RUP-21706  |
|---|
| UDK: | 519.17 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | 10.26493/1855-3974.3085.3ea |
|---|
| COBISS.SI-ID: | 232776195 |
|---|
| Datum objave v RUP: | 10.09.2025 |
|---|
| Število ogledov: | 288 |
|---|
| Število prenosov: | 2 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
