On the expansion of Hanoi graphs

The famous Tower of Hanoi puzzle involves moving n discs of distinct sizes from one of p≥ 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ₚⁿ, whose pⁿ 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)ⁿ) and Ω(n(1-p)/2(p-2)ⁿ) on the treewidth of this graph for fixed p ≥ 3. In this paper we show that the upper bound is tight, by giving a matching lower bound of Ω((p-2)ⁿ) for the expansion of Hₚⁿ. 18 pages, 5 figures