The worst Hanoi graphs
The "Towers of Hanoi" is a problem that has been extensively studied and frequently generalized. We are interested in its generalization to arbitrary directed graphs and ask how many moves are required in a given graph to move n disks from the starting peg to the destination peg. Not all directed graphs allow solving this problem; we will call those graphs that do Hanoi graphs. We settle the question of what are the Hanoi graphs that require the largest number of moves. (C) 2013 Elsevier B.V. All rights reserved.
towers of hanoi maximal number of moves