 Maximal Wiener index for graphs with prescribed number of blocksStéphane Bessy, François Dross, Katarína Hriňáková, Martin Knor and Riste Škrekovski Applied Mathematics and Computation, 2020, vol. 380, issue C Abstract: Wiener index, which is defined as the sum of distances between all unordered pairs of vertices, is one of the oldest and most popular molecular descriptors. It is known that among graphs on n vertices that have just one block, the n-cycle has the biggest Wiener index. In a previous work of the same authors, it was shown that among all graphs on n vertices which have p ≥ 2 blocks, the maximum Wiener index is attained by a graph composed of two cycles Ca and Cb joined by a path of length p−2 (possibly a and b are of size 2). In this paper we elaborate further this result and determine the sizes of a and b in the extremal graphs for each n and p. We distinguish six cases with crucial values being 5p−7 and 5p−8. Roughly speaking, if n bigger than 5p−7, then the extremal graphs is obtained for a=2. i.e. the graph is a path glued to a cycle. For values n=5p−8 and 5p−7, we have more than one extremal graph. And, when n<5p−8, the extremal graphs is again unique with a and b being equal or almost equal depending of the congruence of n−p modulo 4. We also showed unimodal property of a behaviour of Wiener index. Date: 2020 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:380:y:2020:i:c:s0096300320302435 DOI: 10.1016/j.amc.2020.125274 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.