A STRATIFICATION OF THE HANOI GRAPH FOR 4 PEGS

Abstract. For the Tower of Hanoi problem, it has been found that it is possible to construct a nice graph with legal states of the Tower of Hanoi as the vertices and legal moves between legal states as the edges between corresponding vertices. This “Hanoi graph ” we denote by Hkn for k pegs and n disks. Our motivation is to describe the properties of this graph for k ≥ 4 and to describe a class of graphs called Stratified Hanoi graphs, appropriately denoted by SHkn, which will ultimately be useful in visualizing the Frame-Stewart algorithm. 1. Background Information In this article, we will follow the convention of [POOLE] to label vertices. Our motivation is to describe a class of graphs called Hanoi graphs, denoted by Hkn for k pegs and n disks, and to ultimately describe Stratified Hanoi graphs, appropriately denoted by SHkn for k pegs and n disks. In order to do that, in this section we will introduce some notation and definitions that we will use throughout this article. Definition 1.1. A legal state is a configuration of n disks on the k pegs in which each disk is either on top of a larger disk or on an empty peg. Let us label the pegs 0, 1, · · · , k − 1 and the disks from smallest to largest 0, 1, · · · , n−1. We label each legal state with an n-bit k-ary string an−1an−2...a0 where ai ∈ {0, 1, · · · , k − 1} and ai = j if disk i lies on peg j. It is not difficult to see how this labeling is useful, because each string corresponds to a unique legal state. In this article, we will denote the vertex set of a graph G by V (G) and the edge set of G by E(G). Definition 1.2. A legal move from one legal state to another legal state is achieved by moving exactly one disk from one peg to another peg under the following rules. (1) A disk can be moved onto a larger disk. (2) A disk can be moved onto an empty peg. (3) A disk cannot be moved onto a smaller disk. Definition 1.3. Let k,n be positive integers. We define Hkn as a graph such that V (Hkn) is the set of vertices each labeled by an n-bit k-ary string which corresponds to a unique legal state, and E(Hkn) is the set of edges each of which can only exist between two vertices if there exists a legal move between their corresponding legal states. We can see that |V (Hkn) | = kn