Fibonacci Cubes have been an extremely popular area of research since the 1990s. This unique compendium features the state of research into Fibonacci Cubes. It expands the knowledge in graph theoretic and combinatorial properties of Fibonacci Cubes and their variants. By highlighting various approaches with numerous examples, it provides a fundamental source for further research in the field. This useful reference text surely benefits advanced students in computer science and mathematics and serves as an archival record of the current state of the field.
Author(s): Ömer Eğecioğlu, Sandi Klavžar, Michel Mollard
Publisher: World Scientific
Year: 2023
Language: English
Pages: 302
City: Singapore
Contents
Preface
1. Liber Abaci and the Fibonacci Sequence
1.1 Liber Abaci
1.2 Fibonacci Numbers in Nature
1.3 Fibonacci Identities and Induction
1.4 Fibonacci Strings
1.5 Fibonacci Representations
1.6 Compositions
1.7 Tilings
1.8 The Golden Mean
1.9 Binet Formula
1.10 Lucas Numbers
2. Formal Languages and Generating Functions
2.1 Generating Functions
2.2 Elements of Formal Languages
2.3 Generating Functions for Fibonacci and Lucas Numbers
2.4 Further Examples on Generating Functions
2.5 Exponential Generating Functions
2.6 Fibonacci Polynomials
3. Structure of Fibonacci Cubes
3.1 Glossary of Graph Theory
3.2 Fibonacci Cubes
3.3 Fundamental Decomposition
3.4 Order and Size
3.5 Digression: Greene and Wilf Theory
3.6 Sequence of Degrees
3.7 Connectivity
3.8 Symmetry
3.9 Linear Permutations
4. Paths and Cycles in Fibonacci Cubes
4.1 Distance and Related Concepts
4.2 Eccentricity Sequence and Fibonacci Trees
4.3 Hamiltonicity
4.4 Diametral Shortest Paths in Γn
4.4.1 Alternating Permutations and Euler Numbers
4.4.2 The Main Bijection
4.5 Short Induced Paths and Cycles
4.5.1 Enumerating Induced 2-Paths
4.5.2 Enumerating Induced 3-Paths
4.5.3 Enumerating Induced 6-Cycles
4.5.4 Enumerating Induced 8-Cycles
5. Counting Substructures of Fibonacci Cubes
5.1 Cube Polynomial
5.1.1 Roots, Unimodality and Divisibility of CΓn(x)
5.2 Maximal Hypercubes in Fibonacci Cubes
5.3 Disjoint Hypercubes in Γn
5.4 q-Cube Enumerator Polynomial
5.4.1 q-Analogues of Fibonacci Numbers
5.4.2 q-Cube Polynomial
5.4.3 Example Calculations
5.4.4 The Main Recursion
5.4.5 Convolutions
5.4.6 Divisibility Properties of CΓn(x, q)
5.5 Boundary Enumerator Polynomial
5.5.1 An Example
5.5.2 Derivation of the Generating Function
5.5.3 Some Specializations
6. Characterizations and Recognition
6.1 Fibonacci Cubes as Simplex Graphs
6.2 Fibonacci Cubes as Resonance Graphs
6.3 Recognition of Fibonacci Cubes in Linear Time
6.3.1 Fibonacci Cubes are Median Graphs
6.3.2 Characterization Among Median Graphs
6.3.3 Recognition Algorithm
7. Invariants of Fibonacci Cubes
7.1 Domination-Type Invariants
7.2 Wiener Index
7.3 Irregularity
7.3.1 Irregularity Polynomial
7.3.2 A Bijection for irr(Γn)
7.4 Mostar Index
7.4.1 Mostar Index of Fibonacci Cubes
7.4.2 A Closed Formula for Mo(Γn)
7.4.3 Connection to Wiener Index
8. Lucas Cubes
8.1 Decomposition, Order, and Size
8.2 Sequence of Degrees
8.3 Connectivity and Symmetry
8.4 Distance
8.5 Hamiltonicity
8.6 Diametral Shortest Paths
8.7 Counting Substructures
8.7.1 Cube Polynomial
8.7.2 Maximal Hypercubes
8.7.3 q-Cube Polynomial
8.8 Characterizations and Recognition
8.8.1 Lucas Cubes as Resonance Graphs
8.9 Invariants
8.9.1 Domination-Type Invariants
8.9.2 Irregularity
8.9.3 Wiener Index
8.9.4 Mostar Index
8.10 Alternate Lucas Cubes
8.10.1 Enumerative Properties
8.10.1.1 The Size
8.10.1.2 Number of Vertices by Weight
8.10.1.3 Degree Sequences
8.10.2 q-Cube Polynomial
8.10.3 Maximal Hypercubes and Irregularity Polynomial
8.10.4 Additional Properties
8.10.5 Wiener Index and Mostar Index
8.10.6 Diametral Shortest Paths
9. Variations on Fibonacci Cubes
9.1 Generalized Fibonacci Cubes
9.2 Good and Bad Words
9.3 Perfect Codes in Generalized Fibonacci Cubes
9.4 Pell Graphs
9.5 k-Fibonacci Cubes
9.5.1 Examples for Small k
9.5.2 Basic Properties
9.5.3 Degree Polynomials of Γkn
9.5.4 Number of Hypercubes in Γkn
9.5.5 Diameter and Radius
9.5.6 Domination-Type Invariants
9.6 Fibonacci-run Graphs
9.6.1 Order and Decomposition
9.6.2 Size
9.6.3 Diameter
9.6.4 Hamiltonicity, Radius and Center
9.6.5 Up-Degrees and Down-Degrees
9.6.6 q-Cube Polynomial
9.6.7 Up-Down Degree Enumerator Polynomial
9.7 Cube-Complement of Fibonacci Cubes
9.8 Daisy Cubes
9.8.1 Examples, Properties, Characterizations
9.8.2 Distance Cube Polynomial
9.8.3 Pell Graphs as Daisy Cubes
9.8.4 Maximal Hypercubes and an Application
9.8.5 Wiener Index and Mostar Index
9.8.6 Applications in Chemistry and Quantum Physics
9.9 Fibonacci p-Cubes
10. Asymptotic Properties
10.1 Order
10.2 Size
10.3 Average Degree and Average Eccentricity
10.4 Average Distance
10.5 Mostar Index
10.6 Irregularity
10.7 Boundary of Hypercubes
11. Further Avenues of Research
11.1 Chromatic Polynomial
11.2 Isoperimetric Number
11.3 Spanning Trees
11.4 Independence Polynomial
Appendix A The graphs of Γ7 through Γ10
Bibliography
Subject Index
Author Index
Notation Index
