Document Open Access Logo

On the Treewidth of Hanoi Graphs

Authors David Eppstein, Daniel Frishberg , William Maxwell

PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.13.pdf
  • Filesize: 0.6 MB
  • 21 pages

Document Identifiers

Author Details

David Eppstein
  • University of California, Irvine, CA, USA
Daniel Frishberg
  • University of California, Irvine, CA, USA
William Maxwell
  • Oregon State University, Corvallis, OR, USA

Funding

This research was supported in part by NSF grants CCF-1618301, CCF-1616248, and CCF-1617951.

Acknowledgements

Some of the results in the section on three-peg Hanoi graphs were previously announced on a web forum [Eppstein, 2016].

Cite As Get BibTex

David Eppstein, Daniel Frishberg, and William Maxwell. On the Treewidth of Hanoi Graphs. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FUN.2021.13

Abstract

The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • Hanoi graph
  • Treewidth
  • Graph separators
  • Kneser graph
  • Vertex expansion
  • Haven
  • Tensor product

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Danielle Arett and Suzanne Dorée. Coloring and counting on the tower of Hanoi graphs. Mathematics Magazine, 83(3):200-209, 2010. URL: https://doi.org/10.4169/002557010x494841.
  2. Stefan Arnborg, Andrzej Proskurowski, and Derek G. Corneil. Forbidden minors characterization of partial 3-trees. Discrete Mathematics, 80(1):1-19, 1990. URL: https://doi.org/10.1016/0012-365X(90)90292-P.
  3. László Babai and Mario Szegedy. Local expansion of symmetrical graphs. Combinatorics, Probability and Computing, 1(1):1–11, 1992. URL: https://doi.org/10.1017/S0963548300000031.
  4. Hans L. Bodlaender. Fixed-parameter tractability of treewidth and pathwidth. In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx, editors, The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pages 196-227. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-30891-8_12.
  5. Thierry Bousch. La quatrième tour de Hanoï. Bulletin of the Belgian Mathematical Society - Simon Stevin, 21(5):895-912, 2014. URL: http://projecteuclid.org/euclid.bbms/1420071861.
  6. Boštjan Brešar and Simon Špacapan. On the connectivity of the direct product of graphs. The Australasian Journal of Combinatorics, 41:45-56, 2008. URL: https://ajc.maths.uq.edu.au/pdf/41/ajc_v41_p045.pdf.
  7. David Eppstein. Treewidth of deep Sierpiński sieve graph. Theoretical Computer Science Stack Exchange. URL: https://cstheory.stackexchange.com/q/36542.
  8. David Eppstein and Elham Havvaei. Parameterized leaf power recognition via embedding into graph products. In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1-16:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.16.
  9. Jeff Erickson. Computational topology: Treewidth. Lecture Notes, 2009. URL: http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/treewidth.pdf.
  10. Andreas M. Hinz et al. The Tower of Hanoi emdash Myths and Maths. Birkhäuser Basel, 2013. Google Scholar
  11. Peter Frankl. A new short proof for the Kruskal-Katona theorem. Discrete Mathematics, 48(2-3):327-329, 1984. URL: https://doi.org/10.1016/0012-365X(84)90193-6.
  12. Daniel J. Harvey and David R. Wood. Treewidth of the Kneser Graph and the Erdős-Ko-Rado theorem. Electronic Journal of Combinatorics, 21(1):P1.48, 2014. URL: https://doi.org/10.37236/3971.
  13. Wilfried Imrich, Sandi Klavžar, and Douglas F. Rall. Topics in Graph Theory: Graphs and Their Cartesian Product. A K Peters, 2008. Google Scholar
  14. Kyohei Kozawa, Yota Otachi, and Koichi Yamazaki. Lower bounds for treewidth of product graphs. Discrete Applied Mathematics, 162(C):251–258, January 2014. Google Scholar
  15. L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319-324, 1978. URL: https://doi.org/10.1016/0097-3165(78)90022-5.
  16. L. Lovász. Combinatorial Problems and Exercises. AMS/Chelsea publication. North-Holland Publishing Company, 1993. Google Scholar
  17. J. Nešetřil and P. Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  18. Miodrag S. Petković. Famous Puzzles of Great Mathematicians. American Mathematical Society, 2009. Google Scholar
  19. Paul D. Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B, 58(1):22-33, 1993. URL: https://doi.org/10.1006/jctb.1993.1027.
  20. B. M. Stewart and J. S. Frame. Problem 3918 and solution. The American Mathematical Monthly, 48(3):216-219, 1941. URL: https://doi.org/10.2307/2304268.
  21. Mario Valencia-Pabon and Juan-Carlos Vera. On the diameter of Kneser graphs. Discrete Mathematics, 305(1-3):383-385, 2005. URL: https://doi.org/10.1016/j.disc.2005.10.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact