Generalized fibonacci cubes are mostly hamiltonian
Jenshiuh Liu, Wen-Jing Hsu, Moon Jung Chung · Journal of Graph Theory · 1994
Abstract The Hamiltonian problem is to determine whether a graph contains a spanning (Hamiltonian) path or cycle. Here we study the Hamiltonian problem for the generalized Fibonacci cubes , which are a new family of graphs that have applications in interconnection topologies [J. Liuand W.‐J. Hsu, „Distributed Algorithms for Shortest‐Path, Deadlock‐Free Routing and Broadcasting in a Class of Interconnection Topologies,”︁ International Parallel Processing Symposium (1992)]. We show that each member of this family contains a Hamiltonian path. Furthermore, we also characterize the members of this family that contain a Hamiltonian cycle.