Exact diameter of the leaf-slide graph on labelled trees
For $n \ge 3$ let $G_n$ be the graph whose vertices are the trees on the labelled vertex set $[n] = \{1, \dots, n\}$, two trees being adjacent when one is obtained from the other by a single leaf slide: for a leaf $v$ with neighbour $w$ and a neighbour $u \ne v$ of $w$, delete the edge $\{v, w\}$ and insert $\{v, u\}$. Labels are fixed and each slide counts once, so the distance between two trees is the least number of slides transforming one into the other. $G_n$ is the $1$-skeleton of Kozlov's network realignment complex, which deformation retracts onto the complete graph $K_n$; in particular $G_n$ is connected. Klatt, Papadopoulos and Raffelsiefen proved $$\left\lfloor \frac{3n^2 - 4n}{8} \right\rfloor \le \operatorname{diam}(G_n) \le \frac{n^2}{2} - n \quad (n \text{ even}), \qquad \left\lfloor \frac{3n^2 - 6n}{8} \right\rfloor \le \operatorname{diam}(G_n) \le \frac{n^2 - 1}{2} - n \quad (n \text{ odd}),$$ so that $\operatorname{diam}(G_n) \le \lfloor n^2/2 \rfloor - n$ for every $n$, and found by computation that the upper bound is the diameter for $6 \le n \le 9$.
Problem. Is $$\operatorname{diam}(G_n) = \left\lfloor \frac{n^2}{2} \right\rfloor - n$$ for every integer $n \ge 6$?
Source: Kozlov (2025), Open Question 2.5, who asks for a formula for the diameter; the value is the upper bound of Klatt, Papadopoulos and Raffelsiefen (2026), whose computations suggest that it is attained for n ≥ 6. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- AT
- Keywords
- AIM Open Applied Problems, labelled trees, network realignment complexes, reconfiguration graphs
References
@article{kozlov2025,
author = {Kozlov, Dmitry N.},
title = {Network realignment complexes},
journal = {J. Appl. Comput. Topol.},
volume = {9},
number = {1},
year = {2025},
pages = {8},
doi = {10.1007/s41468-025-00204-0},
}
@misc{klatt2026,
author = {Klatt, Fabienne and Papadopoulos, Iason and Raffelsiefen, Marc},
title = {Network Realignment Complexes over General Graphs},
year = {2026},
eprint = {2607.07404},
archivePrefix = {arXiv},
}
@misc{aim-network-realignment-diameter,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Exact diameter of the leaf-slide graph on labelled trees}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/503-network-realignment-diameter.md},
note = {Entry 503 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00880, "Exact diameter of the leaf-slide graph on labelled trees", clopen.solutions.