On the treewidth of Hanoi graphs.

• Analysis of Hanoi graphs , which arise from the classic Tower of Hanoi puzzle. • Nearly tight upper and lower bounds on the treewidth of these graphs. • An extension of the Kneser graph and a proof that its treewidth is nearly linear. • A new proof of a known lower bound on the treewidth of tensor products of graphs. The objective of the well-known Tower of Hanoi puzzle is to move a set of discs one at a time from one of a set of pegs to another, while keeping the discs 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. [ABSTRACT FROM AUTHOR]