2026-10-12T16:19:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12774 2024-03-06T09:49:09Z ddc:004 open_access

On the Treewidth of Hanoi Graphs Eppstein, David Frishberg, Daniel Maxwell, William Hanoi graph Treewidth Graph separators Kneser graph Vertex expansion Haven Tensor product 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Eppstein and Daniel Frishberg and William Maxwell 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.13 urn:nbn:de:0030-drops-127741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.13 eng https://creativecommons.org/licenses/by/3.0/legalcode