文章基本信息

标题：On the Treewidth of Hanoi Graphs
本地全文：下载
作者：David Eppstein ; Daniel Frishberg ; William Maxwell 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：157
页码：13:1-13:21
DOI：10.4230/LIPIcs.FUN.2021.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Hanoi graph; Treewidth; Graph separators; Kneser graph; Vertex expansion; Haven; Tensor product