Some results on the Wiener index related to the Šoltés problem of graphs

2023/11/26 by Dobrynin, Andrey A., Vorob'ev, Konstantin V.
#05C09 #05C12 #05C92 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2311.15144

Abstract

The Wiener index, W(G), of a connected graph G is the sum of distances between its vertices. In 2021, Akhmejanova et al. posed the problem of finding graphs G with large R_m(G)= |\v∈ V(G) | W(G)-W(G-v)=m ∈ ℤ \|/ |V(G)|. It is shown that there is a graph G with R_m(G) > 1/2 for any integer m ≥ 0. In particular, there is a regular graph of even degree with this property for any odd m ≥ 1. The proposed approach allows to construct new families of graphs G with R₀(G) → 1/2 when the order of G increases.

Related

• Wiener index and graphs, almost half of whose vertices satisfy Šoltés property
• An upper bound on the Wiener Index of a k-connected graph
• Wiener Index of Quadrangulation Graphs
• Selected topics on Wiener index
• The Wiener Index of Signed Graphs