Laceability in Hanoi Graphs

R. A. Daisy Singh, R. Murali

Abstract


The topological structure of an interconnection network can be modelled by a connected, simple and undirected graph \(G=(V,E)\) where \(V\) represents the set of processors and \(E\) represents the set of communication links. Interconnection networks are used to interconnect the processors of data centres and cluster computers. The study of Hamiltonicity and the related areas such as Hamiltonian laceability and Hamiltonian connectedness has lot of significance in computer networks. A network(graph) is Hamiltonian connected if it contains a Hamiltonian path between two distinct nodes (vertices). In this paper we shall study the laceability properties associated with Hanoi graphs \(H_n\). To be more specific we shall explore Hamiltonian \(t^*\) connectedness of Hanoi graphs \(H_n\) for \(n\ge3\).

Keywords


Hamiltonian Laceability; Hamiltonian connected

Full Text:

PDF

References


A. M. Hinz and D. Parisse, On the planarity of Hanoi graphs, Expo. Math. 20(3) (2002), 263 – 268.

M. Annapoorna and R. Murali, Hamiltonian Laceability in the line graph of the ((w,1,n,k)) graph, International Journal of Computer Application 5 (2015), 8 – 15.

C.-K. Li and I. Nelson, Perfect codes on the towers of Hanoi graph, Bulletin of the Australian Mathematical Society 57 (3) (1998), 367 – 376, DOI: 10.1017/s0004972700031774.

D. Arett and S. Doree, Colouring and counting on the tower of Hanoi graphs, Mathematical Association of America 83(3) (2010), 200 – 209, DOI: 10.4169/002557010x494841.

D. Berend, A. Sapir and S. Solomon, The Tower of Hanoi problem on path graphs, Discrete Applied Mathematics 160 (2012), 1465 – 1483, DOI: 10.1016/j.dam.2012.02.007.

D. Berend and A. Sapir, The diameter of Hanoi graphs, Information Processing Letters 98(2) (2006), 79 – 85, DOI: 10.1016/j.ipl.2005.12.004.

A. Girisha and R. Murali, Hamiltonian laceability in cyclic product and brick product of cycles, International Journal of Graph Theory 1(1) (2013), 32 – 40.

A. M. Hinz, The tower of Hanoi, Enseign. Math. 35(2) (1989), 289 – 321.

A. M. Hinz, Pascal’s triangle and the tower of Hanoi, Amer. Math. Monthly 99 (1992), 538 – 544, DOI: 10.1080/00029890.1992.11995888.

A. M. Hinz, The tower of Hanoi, in: K. P. Shum, E. J. Taft and Z. X. Wan (eds.), Algebras and Combinatorics, Springer, Singapore, 277 – 289 (1999).

L. N. Shenoy and R. Murali, Laceability on a class of regular graphs, International Journal of Computational Science and Mathematics 2(3) (2010), 397 – 406.

L. Xuemiao, Towers of Hanoi graphs, International Journal of Computer Mathematics 19(1) (1986), 23 – 38.

R. Kumar and U. Maheswari, Matrix representation of Hanoi graphs, International Journal of Science and Research 4(4) (2015), 173 – 174.

S. Aumann, K. A. M. Gotz, A. M. Hinz and C. Petr, The number of moves of the largest disc in shortest path on Hanoi graphs, The Electronic Journal of Combinatorics 21(4) (2014), 1 – 22.

S. Klavzar and U. Milutinovic, Graphs S(n,k) and a variant of the tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997), 95 – 104, URL: http://dml.cz/dmlcz/127341.




DOI: http://dx.doi.org/10.26713%2Fjims.v11i3-4.789

eISSN 0975-5748; pISSN 0974-875X