Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the expansion of ...
Article

On the expansion of Hanoi graphs

David Eppstein (1), Daniel Frishberg (2), William Maxwell (3)
(1) University of California, Irvine [UCI]
(2) California Polytechnic State University
(3) Oregon State University [OSU]
Download article
Open on arXiv
Submitted on
October 22, 2025
Accepted on
May 2, 2026
Published on
July 4, 2026
Last modified on
July 4, 2026
Volume 28
vol. 28:2
Graph Theory
DOI
10.46298/dmtcs.16770
License
Attribution 4.0 International (CC BY 4.0)
Indicators
167
Views
91
Downloads

On the expansion of Hanoi graphs

David Eppstein (1), Daniel Frishberg (2), William Maxwell (3)
(1) University of California, Irvine [UCI]
(2) California Polytechnic State University
(3) Oregon State University [OSU]
Abstract
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
Keywords
  • Combinatorics
  • Discrete Mathematics
Preview
Loading PDF preview...
References

  1. N. Anari, K. Liu, S. O. Gharan, and C. Vinzant. Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), 2019.

    DOI : 10.1145/3313276.3316385

  2. S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM (JACM), 2009.

    DOI : 10.1145/1502793.1502794

  3. L. Babai and M. Szegedy. Local expansion of symmetrical graphs. Combinatorics, Probability and Computing, 1992.

    DOI : 10.1017/s0963548300000031

  4. H. L. Bodlaender. The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, chapter Fixed-Parameter tractability of treewidth and pathwidth. Springer-Verlag, 2012.

    DOI : 10.1007/978-3-642-30891-8_12

  5. D. Eppstein and D. Frishberg. Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs. In 34th International Symposium on Algorithms and Computa- tion (ISAAC 2023), 2023.

    DOI : 10.4230/LIPIcs.ISAAC.2023

  6. D. Eppstein and D. Frishberg. Improved Mixing for the Convex Polygon Triangulation Flip Walk. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), 2023.

    DOI : 10.4230/LIPIcs.ICALP.2023

  7. D. Eppstein, D. Frishberg, and W. Maxwell. On the treewidth of Hanoi graphs. Theoretical Computer Science, 2022.

    DOI : 10.1016/j.tcs.2021.12.014

  8. J. Erickson. Computational topology: Treewidth. Lecture Notes, 2009.

    DOI : 10.1007/bfb0045389

  9. D. J. Harvey and D. R. Wood. Treewidth of the Kneser Graph and the Erdős-Ko-Rado theorem. Electronic Journal of Combinatorics, 2014.

    DOI : 10.37236/3971

  10. A. M. Hinz, U. Milutinović, S. Klavžar, and C. Petr. The Tower of Hanoi-Myths and Maths. Springer, 2018.

  11. W. Imrich, S. Klavžar, and D. F. Rall. Topics in Graph Theory: Graphs and Their Cartesian Product. A K Peters, 2008.

    DOI : 10.1002/jgt.20190

  12. M. Jerrum, J.-B. Son, P. Tetali, and E. Vigoda. Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains. The Annals of Applied Probability, 2004.

    DOI : 10.1214/105051604000000639

  13. V. Kaibel. On the expansion of graphs of 0/1-polytopes. In The Sharpest Cut: The Impact of Manfred Padberg and His Work, pages 199-216. SIAM, 2004.

    DOI : 10.1137/1.9780898718805.ch13

  14. D. A. Levin, Y. Peres, and E. Wilmer. Markov chains and mixing times. American Mathematical Soc., 2017.

    DOI : 10.1090/mbk/058

  15. K. Liu, M. Cao, and M. Lu. Treewidth of the Generalized Kneser Graphs. Electronic Journal of Combi- natorics, 2022.

    DOI : 10.37236/10035

  16. L. McShine and P. Tetali. On the mixing time of the triangulation walk and other catalan structures. In Randomization Methods in Algorithm Design, 1997.

    DOI : 10.1090/dimacs/043

  17. M. Molloy, B. Reed, and W. Steiger. On the mixing rate of the triangulation walk. In Randomization Methods in Algorithm Design, 1997.

    DOI : 10.1090/dimacs/043/11

  18. A. Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combina- torics, Probability and Computing, 1992.

    DOI : 10.1017/s0963548300000390