Five results on maximizing topological indices in graphs

DOI10.46298/DMTCS.6896zbMATH Open1481.05034arXiv2005.03864OpenAlexW3214490783MaRDI QIDQ5024673FDOQ5024673

Authors: Stijn Cambie 

Publication date: 27 January 2022

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Abstract: In this paper, we prove a collection of results on graphical indices. We determine the extremal graphs attaining the maximal generalized Wiener index (e.g. the hyper-Wiener index) among all graphs with given matching number or independence number. This generalizes some work of Dankelmann, as well as some work of Chung. We also show alternative proofs for two recents results on maximizing the Wiener index and external Wiener index by deriving it from earlier results. We end with proving two conjectures. We prove that the maximum for the difference of the Wiener index and the eccentricity is attained by the path if the order $n$ is at least $9$ and that the maximum weighted Szeged index of graphs of given order is attained by the balanced complete bipartite graphs.

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

Recommendations

• Maximum external Wiener index of graphs
• Maximum Wiener Indices of Unicyclic Graphs of Given Matching Number
• Maximizing Wiener index of graphs with fixed maximum degree
• Maximum values of Szeged index and edge-Szeged index of graphs
• On the extremal Wiener indices of some graphs

zbMATH Keywords

eccentricityextremal graphstopological indicesWiener indexSzeged indexaverage distance

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Chemical graph theory (05C92)

Cited In (6)

• Extremal values of degree-based entropies of bipartite graphs
• Maximum external Wiener index of graphs
• Upper bounds on some indices of graphs with a given matching number
• On extremal graphs of weighted Szeged index
• Connected graphs with maximal Graovac-Ghorbani index
• Corrigendum on Wiener index, Zagreb indices and Harary index of Eulerian graphs

This page was built for publication: Five results on maximizing topological indices in graphs

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