Wiener index and graphs, almost half of whose vertices satisfy Šoltés property

DOI10.1016/J.DAM.2022.09.021MaRDI QIDQ2104919zbMATH OpenOpenAlexFDO

Authors Margarita Akhmejanova, K. I. Ol'mezov, Aleksei Volostnov, Ilya Vorobyev, Konstantin Vorob'ev, Yury Yarovikov

Publication date 8 December 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.08786

zbMATH Keywords

transmissionvertex removingWiener indexŠoltés problem

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12) Chemical graph theory (05C92) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: The Wiener index $W(G)$ of a connected graph $G$ is a sum of distances between all pairs of vertices of $G$. In 1991, v{S}olt'{e}s formulated the problem of finding all graphs $G$ such that for every vertex $v$ the equation $W(G)=W(G-v)$ holds. The cycle $C_{11}$ is the only known graph with this property. In this paper we consider the following relaxation of the original problem: find a graph with a large proportion of vertices such that removing any one of them does not change the Wiener index of a graph. As the main result, we build an infinite series of graphs with the proportion of such vertices tending to $frac12$.

Recommendations

• On the Wiener index of graphs
• On the Wiener index of a graph
• On Wiener and terminal Wiener index of graphs
• On the extremal Wiener indices of some graphs
• scientific article; zbMATH DE number 7690965
• Wiener index of graphs and their line graphs
• Wiener index of some total graphs
• On Wiener and multiplicative Wiener indices of graphs
• On Wiener index of graphs and their line graphs
• The Szeged and the Wiener index of graphs

Cites work

• Graphs preserving Wiener index upon vertex removal
• Graphs whose Wiener index does not change when a specific vertex is removed
• scientific article; zbMATH DE number 90560 (Why is no real title available?)
• Mathematical aspects of Wiener index
• On correlation of hyperbolic volumes of fullerenes with their properties
• Wiener index of trees: Theory and applications

Cited in

(14)

• Graphs preserving total distance upon vertex removal
• The Wiener index of signed graphs
• A relaxed version of Šoltés's problem and cactus graphs
• Graphs preserving Wiener index upon vertex removal
• The deck ratio and self-repairing graphs.
• Some results on the Wiener index related to the Šoltés problem of graphs
• On the preservation of the Wiener index of cubic graphs upon vertex removal
• Selected topics on Wiener index
• On relaxed Šoltés's problem
• Šoltés problem for the Kirchhoff index of a graph
• Towards the essence of Šoltés' problem
• Graphs that preserve Kirchhoff index after the removal of a vertex
• On regular graphs with Šoltés vertices
• Abundancy of z-Šoltés' digraphs

This page was built for publication: Wiener index and graphs, almost half of whose vertices satisfy Šoltés property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104919)