20.500.12556/RUP-21706 On regular graphs with Šoltés vertices Regularni grafi s Šoltésovimi točkami 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. Šoltés problem Wiener index regular graphs cubic graphs Cayley graph Šoltés vertex Šoltésov problem Wienerjev indeks regularen graf kubičen graf Cayleyjev graf Šoltésova točka true false false Založba Univerze na Primorskem Angleški jezik Slovenski jezik Neznano 2025-09-10 13:30:26 2025-09-10 13:30:26 2025-10-21 21:52:36 0000-00-00 00:00:00 2025 0 0 20 str. no. 2, [article no.] P2.01 Vol. 25 2025 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2025-03-10 519.17 1855-3974 10.26493/1855-3974.3085.3ea 232776195 AMC_Basic_Nino_2025.pdf AMC_Basic_Nino_2025.pdf 1 5DE6048F8C858933B9E546F43B36D188 112806188a229383236488b18a7390e0fbcb8ec9b6b4164f10f7cd945def5e5c c5009d16-8e39-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31532 Založba Univerze na Primorskem 0 0 0