Structure of Fibonacci cubes: a survey |
| |
Authors: | Sandi Klavžar |
| |
Institution: | 1. Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia 2. Faculty of Natural Sciences and Mathematics, University of Maribor, Maribor, Slovenia
|
| |
Abstract: | The Fibonacci cube Γ n is the subgraph of the n-cube induced by the binary strings that contain no two consecutive 1s. These graphs are applicable as interconnection networks and in theoretical chemistry, and lead to the Fibonacci dimension of a graph. In this paper a survey on Fibonacci cubes is given with an emphasis on their structure, including representations, recursive construction, hamiltonicity, degree sequence and other enumeration results. Their median nature that leads to a fast recognition algorithm is discussed. The Fibonacci dimension of a graph, studies of graph invariants on Fibonacci cubes, and related classes of graphs are also presented. Along the way some new short proofs are given. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|