graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

and

recreational mathematics Recreational mathematics is mathematics carried out for recreation (entertainment) rather than as a strictly research and application-based professional activity or as a part of a student's formal education. Although it is not necessarily limited ...

, the Hanoi graphs are

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

s whose vertices represent the possible states of the

Tower of Hanoi The Tower of Hanoi (also called The problem of Benares Temple or Tower of Brahma or Lucas' Tower and sometimes pluralized as Towers, or simply pyramid puzzle) is a mathematical game or puzzle consisting of three rods and a number of disks of va ...

puzzle, and whose edges represent allowable moves between pairs of states.

Construction

The puzzle consists of a set of disks of different sizes, placed in increasing order of size on a fixed set of towers. The Hanoi graph for a puzzle with

n

disks on

k

towers is denoted

H^n_k

. Each state of the puzzle is determined by the choice of one tower for each disk, so the graph has

k^n

vertices. In the moves of the puzzle, the smallest disk on one tower is moved either to an unoccupied tower or to a tower whose smallest disk is larger. If there are

u

unoccupied towers, the number of allowable moves is :

\binom-\binom,

which ranges from a maximum of

\tbinom

(when

u

is zero or one and

\tbinom

is zero) to

k-1

(when all disks are on one tower and

u

k-1

). Therefore, the degrees of the vertices in the Hanoi graph range from a maximum of

\tbinom

to a minimum of

k-1

. The total number of edges is :

\frac\binom\bigl(k^n-(k-2)^n\bigr).

For

k=0

(no disks) there is only one state of the puzzle and one vertex of the graph. For

k > 0

, the Hanoi graph

H^n_k

can be decomposed into

k

copies of the smaller Hanoi graph

H^_k

, one for each placement of the largest disk. These copies are connected to each other only at states where the largest disk is free to move: it is the only disk in its tower, and some other tower is unoccupied.

General properties

lang=cy, 300px,

H^3_3

with 12 edges deleted to yield a Hamiltonian cycle Every Hanoi graph contains a

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

. The Hanoi graph

H^1_k

is a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

k

vertices. Because they contain complete graphs, all larger Hanoi graphs

H^n_k

require at least

k

colors in any

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

. They may be colored with exactly

k

colors by summing the indexes of the towers containing each disk, and using the sum modulo

k

as the color.

Three towers

A particular case of the Hanoi graphs that has been well studied since the work of is the case of the three-tower Hanoi graphs,

H^n_3

. These graphs have vertices () and

edges Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

(). They are

penny graph In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circ ...

s (the

contact graph In the mathematical area of graph theory, a contact graph or tangency graph is a graph whose vertices are represented by geometric objects (e.g. curves, line segments, or polygons), and whose edges correspond to two objects touching (but not cross ...

s of non-overlapping unit disks in the plane), with an arrangement of disks that resembles the Sierpinski triangle. One way of constructing this arrangement is to arrange the numbers of

Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...

on the points of a

hexagonal lattice The hexagonal lattice or triangular lattice is one of the five two-dimensional Bravais lattice types. The symmetry category of the lattice is wallpaper group p6m. The primitive translation vectors of the hexagonal lattice form an angle of 120° ...

, with unit spacing, and place a unit disk on each point whose number is odd. The

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...

of these graphs, and the length of the solution to the standard form of the Tower of Hanoi puzzle (in which the disks all start on one tower and must all move to one other tower) is

2^-1

More than three towers

For

k > 3

, the structure of the Hanoi graphs is not as well understood, and the diameter of these graphs is unknown. When

k > 4

and

n > 0

or when

k = 4

and

n > 2

, these graphs are nonplanar.

References

{{reflist, refs= {{citation , last1 = Arett , first1 = Danielle , last2 = Dorée , first2 = Suzanne , author2-link = Suzanne Dorée , doi = 10.4169/002557010X494841 , issue = 3 , journal = Mathematics Magazine , mr = 2668333 , pages = 200–209 , title = Coloring and counting on the Tower of Hanoi graphs , volume = 83 , year = 2010, s2cid = 120868360 {{citation , last = Stewart , first = Ian , author-link = Ian Stewart (mathematician) , isbn = 0-486-43181-9 , mr = 2046372 , contribution = Chapter 1: The Lion, the Llama, and the Lettuce , publisher = Dover Publications , location = Mineola, NY , title = Another Fine Math You've Got Me Into , year = 2003 {{citation , last1 = Hinz , first1 = Andreas M. , last2 = Klavžar , first2 = Sandi , author2-link = Sandi Klavžar , last3 = Petr , first3 = Ciril , contribution = 2.3 Hanoi Graphs , doi = 10.1007/978-3-319-73779-9 , edition = 2nd , isbn = 978-3-319-73778-2 , location = Cham , mr = 3791459 , page = 120 , publisher = Birkhäuser , title = The tower of Hanoi—myths and maths , title-link = The Tower of Hanoi – Myths and Maths , year = 2018 {{citation , last1 = Hinz , first1 = Andreas M. , last2 = Parisse , first2 = Daniele , doi = 10.1016/S0723-0869(02)80023-8 , issue = 3 , journal = Expositiones Mathematicae , mr = 1924112 , pages = 263–268 , title = On the planarity of Hanoi graphs , volume = 20 , year = 2002, doi-access = free {{citation , last1 = Imrich , first1 = Wilfried , author1-link = Wilfried Imrich , last2 = Klavžar , first2 = Sandi , author2-link = Sandi Klavžar , last3 = Rall , first3 = Douglas F. , contribution = 2.2 Hanoi Graphs , isbn = 978-1-56881-429-2 , location = Wellesley, MA , mr = 2468851 , pages = 13–15 , publisher = A K Peters , title = Topics in Graph Theory: Graphs and their Cartesian Product , year = 2008 {{citation , last1 = Scorer , first1 = R. S. , last2 = Grundy , first2 = P. M. , author2-link = Patrick Michael Grundy , last3 = Smith , first3 = C. A. B. , author3-link = Cedric Smith (statistician) , date = July 1944 , doi = 10.2307/3606393 , issue = 280 , journal = The Mathematical Gazette , page = 96 , title = Some binary games , volume = 28, jstor = 3606393 Parametric families of graphs Planar graphs

Construction

General properties

Three towers

More than three towers

See also

References