Maximal hypercubes in Fibonacci and Lucas cubes

2012/01/06 by Mollard, Michel
Computer Science · Mathematics · Physics and Astronomy · #Advanced Mathematical Theories and Applications #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems

paper · doi:10.48550/arxiv.1201.1494

openalex publication_date 2012/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Fibonacci cube Γ_n is the subgraph of the hypercube induced by the binary strings that contain no two consecutive 1's. The Lucas cube Λ_n is obtained from Γ_n by removing vertices that start and end with 1. We characterize maximal induced hypercubes in Γ_n and Λ_n and deduce for any p≤ n the number of maximal p-dimensional hypercubes in these graphs.

Related

• p-th order generalized Fibonacci cubes and maximal cubes in Fibonacci p-cubes
• Some new results about Fibonacci p-cubes
• On Disjoint hypercubes in Fibonacci cubes
• Edges in Fibonacci cubes, Lucas cubes and complements
• Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes