On the expansion of Hanoi graphs
Discrete Mathematics & Theoretical Computer Science · 04.07.2026 · vol. 28:2 (Graph Theory)
DOI: 10.46298/dmtcs.16770 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 04.07.2026. Verfasst von David Eppstein und 2 weiteren Autor:innen.
Abstract (Originalsprache)
The famous Tower of Hanoi puzzle involves moving $n$ discs of distinct sizes from one of $p\geq 3$ pegs (traditionally $p=3$) to another of the pegs, subject to the constraints that only one disc may be moved at a time, and no disc can ever be placed on a disc smaller than itself. Much is known about the Hanoi graph $H_p^n$, whose $p^n$ vertices represent the configurations of the puzzle, and whose edges represent the pairs of configurations separated by a single legal move. In a previous paper, the present authors presented nearly tight asymptotic bounds of $O((p-2)^n)$ and $Ω(n^{(1-p)/2}(p-2)^n)$ on the treewidth of this graph for fixed $p \geq 3$. In this paper we show that the upper bound is tight, by giving a matching lower bound of $Ω((p-2)^n)$ for the expansion of $H_p^n$. 18 pages, 5 figures
Zitieren
APA
Eppstein, D., Frishberg, D., & Maxwell, W. (2026). On the expansion of Hanoi graphs. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Graph Theory). https://doi.org/10.46298/dmtcs.16770
Vancouver
Eppstein D, Frishberg D, Maxwell W. On the expansion of Hanoi graphs. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Graph Theory). doi:10.46298/dmtcs.16770
BibTeX
@article{Eppstein2026,
author = {Eppstein, David and Frishberg, Daniel and Maxwell, William},
title = {On the expansion of Hanoi graphs},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:2},
number = {Graph Theory},
doi = {10.46298/dmtcs.16770}
}
EUVIMED