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

Wiener indextransmissionvertex removingŠoltés problem

Mathematics Subject Classification ID

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

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

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

Cited in

(9)

• Graphs preserving Wiener index upon vertex removal
• Selected topics on Wiener index
• On the preservation of the Wiener index of cubic graphs upon vertex removal
• The deck ratio and self-repairing graphs.
• On relaxed Šoltés's problem
• Some results on the Wiener index related to the Šoltés problem of graphs
• A relaxed version of Šoltés's problem and cactus graphs
• Graphs preserving total distance upon vertex removal
• The Wiener index of signed graphs

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)