D-Graphs, Graphs, that Arise from Some Linear Equations

Document Type : Research Paper

Author

School of Mathematical Science, Damghan University, Damghan, Iran;

10.22128/gadm.2024.797.1107

Abstract

Many interesting structures are arising from the Tower of Hanoi puzzle. Some of them increase the number of pegs and some of the others relax the Divine Rule. But all of them accept discs of different diameters. In this paper, we increased the number of available pegs and changed the Divine Rule by considering similar discs, that is, all discs have the same size diameter. From this point of view, the Tower of Hanoi puzzle becomes the distributing of n identical discs (objects) into k distinct labeled pegs (boxes). We modify Lucas’s legend to justify these variations. Each distribution of n discs on k
pegs is a regular state. In a Diophantine Graph, every possible regular state is represented by a vertex. Two vertices are adjacent in a Diophantine Graph if their corresponding states differ by one move. The Diophantine Graphs have shown to possess attractive structures. Since it can be embedded as a subgraph of a Hamming Graph, the Diophantine Graph may find applications in faulttolerant computing.

Keywords