**
**

**Hinz, Andreas M.; Luzar, Borut and Petr, Ciril (2022): The Dudeney-Stockmeyer Conjecture. In: Discrete Applied Mathematics, Vol. 319: pp. 19-26**

**Full text not available from 'Open Access LMU'.**

## Abstract

Consider a variant of the famous Tower of Hanoi problem where moves of the discs are allowed along the edges of a connected simple graph D whose vertices represent the vertical pegs of the puzzle. The task is to transfer a tower of n is an element of N discs from one peg to another according to the well-known rules of the classical game corresponding to D expressionpproximexpressiontely equexpressionl to K-3. Apart from its recreational appeal, the problem brings about fascinating integer sequences engendered by the respective minimum number of moves, i.e. the distance in the canonical metric of the state graph HDn. We construct an algorithm which solves the task for all cases but the exceptional instance of the Linear Tower of Hanoi (i.e. where D is a path graph) in which the transfer is between the two end vertices of D. Optimality of this algorithm is claimed in our central conjecture which is supported by large-scale computational explorations. (C) 2021 Elsevier B.V. All rights reserved.

Item Type: | Journal article |
---|---|

Faculties: | Mathematics, Computer Science and Statistics > Mathematics |

Subjects: | 500 Science > 510 Mathematics |

ISSN: | 0166-218X |

Language: | English |

Item ID: | 111055 |

Date Deposited: | 02. Apr 2024, 07:22 |

Last Modified: | 13. Aug 2024, 12:47 |