Graphs with a given diameter that maximise the Wiener index

Qiang Sun, Barbara Ikica, Riste Škrekovski and Vida Vukašinović

Applied Mathematics and Computation, 2019, vol. 356, issue C, 438-448

Abstract: The Wiener index of a graph is one of the most recognised and very well-researched topological indices, i.e. graph theoretic invariants of molecular graphs. Nonetheless, some interesting questions remain largely unsolved despite being easy to state and comprehend. In this paper, we investigate a long-standing question raised by Plesník in 1984, namely, which graphs with a given diameter d attain the maximum value with respect to the Wiener index. Our approach to the problem is twofold – first we investigate the graphs with diameter smaller than or equal to 4, and then restrict our attention to graphs with diameter equal to n−c for c ≥ 1. Specifically, we provide a complete characterisation of sought-after graphs for 1 ≤ c ≤ 4 and solve the general case for c small enough in comparison to n. Along the way, we state some conjectures and propose an extension to our work.

Keywords: Molecular structure descriptor; Molecular graph; Extremal graphs; Wiener index (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319302267
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:356:y:2019:i:c:p:438-448

DOI: 10.1016/j.amc.2019.03.025

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().