The structure of graphs with given number of blocks and the maximum Wiener index

DOI10.1007/S10878-019-00462-6MaRDI QIDQ2292137zbMATH OpenOpenAlexWikidataFDO

Authors François Dross, Katarína Hriňáková, Martin Knor, Riste Škrekovski, Stéphane Bessy

Publication date 3 February 2020

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

distancegraph theoryWiener index

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12)

Abstract: The Wiener index (the distance) of a connected graph is the sum of distances between all pairs of vertices. In this paper, we study the maximum possible value of this invariant among graphs on $n$ vertices with fixed number of blocks $p$. It is known that among graphs on $n$ vertices that have just one block, the $n$-cycle has the largest Wiener index. And the $n$-path, which has $n-1$ blocks, has the maximum Wiener index in the class of graphs on $n$ vertices. We show that among all graphs on $n$ vertices which have $pge2$ blocks, the maximum Wiener index is attained by a graph composed of two cycles joined by a path (here we admit that one or both cycles can be replaced by a single edge, as in the case $p=n-1$ for example).

Recommendations

• Maximal Wiener index for graphs with prescribed number of blocks
• Wiener polarity index of cycle-block graphs
• The graphs with minimal and maximal Wiener index in a class of bicyclic graphs
• Maximizing Wiener index of graphs with fixed maximum degree
• Ordering trees and connected graphs by their Wiener index

Cites work

• scientific article; zbMATH DE number 90560 (Why is no real title available?)
• A survey on graphs extremal with respect to distance-based topological indices
• Distance in graphs
• Graph theory
• Mathematical aspects of Wiener index
• Maximal Wiener index for graphs with prescribed number of blocks
• On the minimum distance in a \(k\)-vertex set in a graph
• Wiener index of Eulerian graphs
• Wiener index of trees: Theory and applications

Cited in

(5)

• Selected topics on Wiener index
• On the Kirchhoff and the Wiener indices of graphs and block decomposition
• Proof of a conjecture on the Wiener index of Eulerian graphs
• Maximal Wiener index for graphs with prescribed number of blocks
• Graphs with the second and third maximum Wiener indices over the 2-vertex connected graphs

This page was built for publication: The structure of graphs with given number of blocks and the maximum Wiener index

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