The stacking number of a tree
Abstract
Csernák and Soukup introduced the stacking number of a graph: the least integer t≥2 such that every configuration of t pebbles can be transformed by pebbling moves into a configuration supported on one vertex. They conjectured an explicit formula for the stacking number of a tree in terms of the degrees of its vertices and their distances from a chosen root. We prove this conjecture for every finite tree with at least two vertices. We also show that whether a configuration on a tree can be stacked at a given vertex is decided exactly by the sign of an integer score built from recursive branch messages; consequently, stackability can be tested with a linear number of arithmetic operations. The proof combines this criterion with an explicit zero-score obstruction and a weighted cancellation argument for arbitrary nonstackable configurations. The main theorem and the stackability criterion are formalized in Lean 4, and the main theorem has passed Palomar mechanical verification; it is publicly registered as PALOMAR-2026-09-25-000010.
Related
- Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
- Tree Independence Number III. Thetas, Prisms and Stars
- On the Turán number for the Cartesian product of an odd cycle and a tree
- An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs
- Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
BibTeX
@misc{fairfaxball2026stacking,
title = {{The stacking number of a tree}},
author = {John Fairfax-Ball},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.31811},
eprint = {2609.31811},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.31811},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The stacking number of a tree
AU - John Fairfax-Ball
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2609.31811
UR - https://arxiv.org/abs/2609.31811
AB - Csernák and Soukup introduced the stacking number of a graph: the least integer t≥2 such that every configuration of t pebbles can be transformed by pebbling moves into a configuration supported on one vertex. They conjectured an explicit formula for the stacking number of a tree in terms of the degrees of its vertices and their distances from a chosen root. We prove this conjecture for every finite tree with at least two vertices. We also show that whether a configuration on a tree can be stacked at a given vertex is decided exactly by the sign of an integer score built from recursive branch messages; consequently, stackability can be tested with a linear number of arithmetic operations. The proof combines this criterion with an explicit zero-score obstruction and a weighted cancellation argument for arbitrary nonstackable configurations. The main theorem and the stackability criterion are formalized in Lean 4, and the main theorem has passed Palomar mechanical verification; it is publicly registered as PALOMAR-2026-09-25-000010.
ER -