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

DOI10.1016/J.DAM.2022.09.021zbMATH Open1504.05059arXiv2012.08786OpenAlexW4307838004MaRDI QIDQ2104919FDOQ2104919

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)

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$.

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

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

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)

Cites Work

• Wiener index of trees: Theory and applications
• Title not available (Why is that?)
• On correlation of hyperbolic volumes of fullerenes with their properties
• Mathematical aspects of Wiener index
• Graphs whose Wiener index does not change when a specific vertex is removed
• Graphs preserving Wiener index upon vertex removal

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
• On relaxed Šoltés's problem
• The deck ratio and self-repairing graphs.
• 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)