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

DOI10.1007/S10878-019-00462-6zbMATH Open1434.05042arXiv1905.02633OpenAlexW2982031776WikidataQ126983809 ScholiaQ126983809MaRDI QIDQ2292137FDOQ2292137

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

Publication date: 3 February 2020

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

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

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

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

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)

Cites Work

• Graph theory
• Title not available (Why is that?)
• Wiener index of trees: Theory and applications
• Distance in graphs
• Wiener index of Eulerian graphs
• Title not available (Why is that?)
• Maximal Wiener index for graphs with prescribed number of blocks
• Mathematical aspects of Wiener index
• On the minimum distance in a \(k\)-vertex set in a graph

Cited In (4)

• 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

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)