Iskanje po repozitoriju

A+ | A- | | SLO | ENG

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
Objavljeno v DiRROS: 17.04.2025; Ogledov: 151; Prenosov: 57
Celotno besedilo (457,76 KB)
Gradivo ima več datotek! Več...

Povzetek: The Wiener index is defined as the sum of distances between all unordered pairs of vertices in a graph. It is one of the most recognized and well-researched topological indices, which is on the other hand still a very active area of research. This work presents a natural continuation of the paper Mathematical aspects of Wiener index (Ars Math. Contemp., 2016) in which several interesting open questions on the topic were outlined. Here we collect answers gathered so far, give further insights on the topic of extremal values of Wiener index in different settings, and present further intriguing problems and conjectures.
Ključne besede: graph distance, Wiener index, average distance, topological index, molecular descriptor, chemical graph theory
Objavljeno v DiRROS: 20.11.2024; Ogledov: 301; Prenosov: 135
Celotno besedilo (519,71 KB)
Gradivo ima več datotek! Več...