Abstract:The Wiener index of a connected graph is defined as the sum of distances between all its unordered pairs of vertices. Characterising graphs on $n$ vertices with a fixed diameter that maximise the Wiener index is a long-standing open problem. This problem has been resolved fully for trees on $n$ vertices with diameter $d \in \{1,2,3,4,n-3,n-2,n-1\}$ while partial results are available for $d=5$ and $6$. In this context, a conjecture proposed by DeLaViña and Waller has remained open for the last 18 years.
In this paper, we establish a necessary condition for a tree to attain the maximum Wiener index among all trees on $n$ vertices with a given diameter. Using this condition, we characterise the maximal trees for diameter $n-4$ and $n-5$. Furthermore, we prove the DeLaViña Waller conjecture for the classes of graphs having $0,1,2,3$ or $n-4$ cut vertices.
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05C09, 05C12, 05C35, 05C75 |
| Cite as: | arXiv:2605.24855 [math.CO] |
| (or arXiv:2605.24855v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.24855 arXiv-issued DOI via DataCite (pending registration) |
From: Dinesh Pandey [view email]
[v1]
Sun, 24 May 2026 04:22:24 UTC (19 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。