The Hamiltonian Laceability of some Generalized Honeycomb Tori
Li-Yen Hsu, Tung-Yi Lin, Shin-Shin Kao, Theodore E. Simos, George Psihoyios · AIP conference proceedings · 2008
Assume that m, n and s are integers with m⩾2, n⩾4, 0⩽s⩽n and s is of the same parity of m. The generalized honeycomb torus GHT (m,n,s) is recognized as another attractive alternative to existing torus interconnection networks in parallel and distributed applications. It is known that any GHT (m,n,s) is 3‐regular, hamiltonian, bipartite graph. We are interested in two special types of the generalized honeycomb torus, GHT (m,n,n2) and GHT (m,n,0). Let G = GHT(m,n,s), where s∈{n2,0}. We prove that any G is hamiltonian laceable. More precisely, given a pair of vertices P = {u,v|u∈B,v∈W} where B and W are the bipartition of V(G), there exists a path Q between u and v such that Q contains all vertices of G.