Generalized fibonacci cubes are mostly hamiltonian

✍ Scribed by Jenshiuh Liu; Wen-Jing Hsu; Moon Jung Chung

• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 619 KB
• Volume: 18
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190180806

✦ Synopsis

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.