TY - JOUR

T1 - A tour of general Hanoi graphs

AU - Berend, Daniel

AU - Cohen, Liat

AU - Filtser, Omrit

N1 - Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2024/2/1

Y1 - 2024/2/1

N2 - The Tower of Hanoi puzzle has fascinated researchers in mathematics and theoretical computer science for over a hundred years. Many variants of the classical puzzle have been posed, such as allowing more than 3 pegs, and adding restrictions on the possible moves between the pegs. It is natural to view the pegs and allowed moves by means of a graph. The pegs are represented by the vertices of the graph, and the allowed moves by the edges. For each n, this graph yields a graph on the set of all legal configurations of n disks. Thus, the questions about the original puzzle may be reformulated as questions about connectivity and shortest paths in the graph of all configurations. Moreover, it was shown that classical Hanoi graphs are related to several interesting and useful structures such as the Sierpiński gasket and Gray codes, and thus several properties of these graphs were studied, including Hamiltonicity and planarity. In this paper we study these properties, and several others – chromatic number, clique number, and girth – for general Hanoi graphs.

AB - The Tower of Hanoi puzzle has fascinated researchers in mathematics and theoretical computer science for over a hundred years. Many variants of the classical puzzle have been posed, such as allowing more than 3 pegs, and adding restrictions on the possible moves between the pegs. It is natural to view the pegs and allowed moves by means of a graph. The pegs are represented by the vertices of the graph, and the allowed moves by the edges. For each n, this graph yields a graph on the set of all legal configurations of n disks. Thus, the questions about the original puzzle may be reformulated as questions about connectivity and shortest paths in the graph of all configurations. Moreover, it was shown that classical Hanoi graphs are related to several interesting and useful structures such as the Sierpiński gasket and Gray codes, and thus several properties of these graphs were studied, including Hamiltonicity and planarity. In this paper we study these properties, and several others – chromatic number, clique number, and girth – for general Hanoi graphs.

KW - Hamiltonicity

KW - Planarity

KW - Towers of Hanoi

UR - http://www.scopus.com/inward/record.url?scp=85181659941&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2023.114289

DO - 10.1016/j.tcs.2023.114289

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:85181659941

SN - 0304-3975

VL - 983

SP - 114289

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 114289

ER -