On a conjecture of DeLaViña and Waller
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910252376522752 |
|---|---|
| author | Pandey, Dinesh Ravi, Peruvemba Sundaram |
| author_facet | Pandey, Dinesh Ravi, Peruvemba Sundaram |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_24855 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On a conjecture of DeLaViña and Waller Pandey, Dinesh Ravi, Peruvemba Sundaram Combinatorics 05C09, 05C12, 05C35, 05C75 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. |
| title | On a conjecture of DeLaViña and Waller |
| topic | Combinatorics 05C09, 05C12, 05C35, 05C75 |
| url | https://arxiv.org/abs/2605.24855 |