Laceability in the Modified Distance Graph of Grid Graphs


  • M. S. Annapoorna
  • R. Murali
  • B. Shanmukha


A connected graph G is Hamiltonian-t-laceable if there exists in
it a Hamiltonian path between at least one pair of distinct vertices u and v with the property d(u; v) = t; 1 6 t 6 diamG. G is termed t-connected if it is Hamiltonian-t-laceable for all t. In this paper, we show that the modied distance graph of the grid graph Mgr(m; n) for n = m, 4 < m < 11 and for n = 2m, 2 < m < 8 is t-connected.


[1] Fred Buckley and Frank Harary. Distance in Graphs. Addison-Wesley Pub. Co., 1990.

[2] R. Murali and K. S. Harinath. Laceability and Distance Graphs, J. Disc. Math. Sci. Crypt., 4(1)(2001), 77-86.

[3] S. N. Thimmaraju and R. Murali. Laceability in Distance Graphs, J. Anal. Comp., 5(1)(2009), 1-14.

[4] L. N. Shenoy and R. Murali. Laceability on a Class of Regular Graphs. Inter. J. Comp. Sci. Math., 2(3)(2010), 397-406.