On the expansion of Hanoi graphs

Abstract

The famous Tower of Hanoi puzzle involves moving $n$ discs of distinct sizes from one of $p\ge 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 $\Omega (n^{(1-p)/2}(p-2{)}^n)$ on the treewidth of this graph for fixed $p\ge 3$. In this paper we show that the upper bound is tight, by giving a matching lower bound of $\Omega ((p-2{)}^n)$ for the expansion of $H_p^n$.

arXiv comment18 pages, 5 figures