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

Document Type : Research Paper

Author

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

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

References

1. J. P. Bode, A. M. Hinze, Results and open problems on the Tower of Hanoi, Congr. Numer. 139, 113–122 (1999).
2. Y. Dinitz, S. Solomon, Optimal algorithms for Tower of Hanoi problems with relaxed placement rules, In Algorithms and computation, Vol. 4288 of Lecture Notes in Comput. Sci., Springer, Berlin, 2006.
3. H. E. Dudeney, The Canterbury Puzzles and Other Curious Problems, 4th ed., Dover Publications, Inc., New York, 1959.
4. X. Chen, B. Tian, L. Wang, Santa Claus’ towers of Hanoi, Graphs Combin., 23, 153–167 (2007).
5. J. S. Frame, B. M. Stewart, Solution to advanced problem 3819, Amer. Math. Monthly, 48(3), 216–219 (1941).
6. A. M. Hinz, The Tower of Hanoi, Enseign. Math., 2(35), 289–321 (1989).
7. A. M. Hinz, Pascal’s triangle and the tower of Hanoi, Amer. Math. Monthly, 99, 538–544 (1992).
8. A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi-Myths and Maths, Birkhäuser/Springer Basel AG, Basel, 2013.
9. W. Imrich, S. Klavzˇar, D. F. Rall, Topics in Graph Theory, Graphs and Their Cartesian Product, A K Peters, Wellesley Massachusetts, 2008.
10. K. M. Koh, C. C. Chen, Principles and Techniques in Combinatorics, World scientific Publishing Co. thired reprint, 1999.
11. D. B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2002. 
Analytical and Numerical Solutions for Nonlinear Equations
Volume 8, Issue 1
November 2023
Pages 81-96

Files

History

  • Receive Date: 03 March 2024
  • Revise Date: 28 May 2024
  • Accept Date: 09 June 2024

Share

How to cite

Statistics