Sustainable trees
Abstract
Let X be a connected graph and let λ1(X) denote the spectral radius of its adjacency matrix. An edge e of X is sustainable if it can be deleted and replaced by a non-edge so that the resulting graph is connected and its spectral radius does not decrease; X is sustainable if every edge is. We study this edgewise notion of spectral robustness for trees, where each replacement is an elementary exchange between trees on the same vertex set. We establish basic properties of sustainability and exhibit infinite families of sustainable and non-sustainable trees. Our main results concern trees with a vertex of large degree: if T is a tree on n vertices with Δ(T)≥ n/2, then every vertex of maximum degree is a principal vertex, that is, a vertex at which the Perron vector is maximal. Building on this, we prove that every tree with Δ(T)≥ n/2+1 is non-sustainable, and we classify the sustainable trees in the boundary case Δ(T)=n/2: for n≥ 4, the only such trees are the double broom $B(2,n/2,n/2-1)$ and one exceptional tree on eight vertices. We conclude with open problems on the generalized tree-shift order and the asymptotic proportion of sustainable trees.
Related
- Horocyclic products of trees
- Joint partial equidistribution of Farey rays in negatively curved manifolds and trees
- Rare subtree patterns in size-conditioned Bienaymé trees: Poisson approximation and declumping
- Learning Optimal Prescriptive Trees from Observational Data
- Decision trees with optimal joint partitioning
BibTeX
@misc{bencs2026sustainable,
title = {{Sustainable trees}},
author = {Ferenc Bencs and Maarten van Dijk and Krystal Guo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17078},
eprint = {2610.17078},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17078},
}
RIS
TY - UNPB
TI - Sustainable trees
AU - Ferenc Bencs
AU - Maarten van Dijk
AU - Krystal Guo
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17078
UR - https://arxiv.org/abs/2610.17078
AB - Let X be a connected graph and let λ_1(X) denote the spectral radius of its adjacency matrix. An edge e of X is sustainable if it can be deleted and replaced by a non-edge so that the resulting graph is connected and its spectral radius does not decrease; X is sustainable if every edge is. We study this edgewise notion of spectral robustness for trees, where each replacement is an elementary exchange between trees on the same vertex set. We establish basic properties of sustainability and exhibit infinite families of sustainable and non-sustainable trees. Our main results concern trees with a vertex of large degree: if T is a tree on n vertices with Δ(T)≥ n/2, then every vertex of maximum degree is a principal vertex, that is, a vertex at which the Perron vector is maximal. Building on this, we prove that every tree with Δ(T)≥ n/2+1 is non-sustainable, and we classify the sustainable trees in the boundary case Δ(T)=n/2: for n≥ 4, the only such trees are the double broom $B(2,n/2,n/2-1)$ and one exceptional tree on eight vertices. We conclude with open problems on the generalized tree-shift order and the asymptotic proportion of sustainable trees.
ER -