20.500.12556/RUL-168564 On regular graphs with Šoltés vertices 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 true false true Angleški jezik Angleški jezik Članek v reviji 2025-04-17 10:05:10 2025-04-17 10:05:15 2025-04-18 04:34:09 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-01-01 519.17 1855-3966 10.26493/1855-3974.3085.3ea 232776195 amc_3085.pdf amc_3085.pdf 1 5DE6048F8C858933B9E546F43B36D188 112806188a229383236488b18a7390e0fbcb8ec9b6b4164f10f7cd945def5e5c 4e29418a-1b62-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=208631 https://amc-journal.eu/index.php/amc/article/view/3085 1 91bf9432-1b61-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=208630 Fakulteta za matematiko in fiziko 0 0 0