Graphs with the second and third maximum Wiener indices over the 2-vertex connected graphs

DOI10.1016/J.DAM.2020.03.032zbMATH Open1443.05039arXiv1905.04291OpenAlexW3015893795MaRDI QIDQ777380FDOQ777380

François Dross, Stéphane Bessy, Riste Škrekovski, Martin Knor

Publication date: 7 July 2020

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

Abstract: Wiener index, defined as the sum of distances between all unordered pairs of vertices, is one of the most popular molecular descriptors. It is well known that among 2-vertex connected graphs on $nge3$ vertices, the cycle $C_n$ attains the maximum value of Wiener index. We show that the second maximum graph is obtained from $C_n$ by introducing a new edge that connects two vertices at distance two on the cycle if $ne6$. If $nge11$, the third maximum graph is obtained from a $4$-cycle by connecting opposite vertices by a path of length $n-3$. We completely describe also the situation for $nle10$.

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

Recommendations

• Bicyclic graphs with the second up to seventh largest Wiener indices.
• Ordering trees and connected graphs by their Wiener index
• Unicyclic graphs with second largest Wiener index
• Maximal Wiener index for graphs with prescribed number of blocks
• The structure of graphs with given number of blocks and the maximum Wiener index

zbMATH Keywords

distanceWiener indextransmission2-vertex connected graphsGross status

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12)

Cites Work

• Title not available (Why is that?)
• Wiener index of trees: Theory and applications
• Distance in graphs
• Title not available (Why is that?)
• Ordering trees by their Wiener indices
• The trees on \(n\geq 9\) vertices with the first to seventeenth greatest Wiener indices are chemical trees
• Title not available (Why is that?)
• Mathematical aspects of Wiener index
• Title not available (Why is that?)

Cited In (7)

• Selected topics on Wiener index
• Proof of a conjecture on the Wiener index of Eulerian graphs
• Title not available (Why is that?)
• The number of subtrees in graphs with given number of cut edges
• Maximum number of subtrees in cacti and block graphs
• Wiener Index, Kirchhoff Index in Graphs with Given Girth and Maximum Degree
• Title not available (Why is that?)

This page was built for publication: Graphs with the second and third maximum Wiener indices over the 2-vertex connected graphs

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