EUVIMEDEUVIMED entdecken
Crossref

On the expansion of Hanoi graphs

David Eppstein, Daniel Frishberg, William Maxwell

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →