On disjoint hypercubes in Fibonacci cubes

The Fibonacci cube of dimension n, denoted as Γn, is the subgraph of n-cube Qn induced by vertices with no consecutive 1’s. We study the maximum number of disjoint subgraphs in Γn isomorphic to Qk, and denote this number by qk(n). We prove several recursive results for qk(n), in particular we prove...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2015-08, Vol.190-191, p.50-55
Main Authors: Gravier, Sylvain, Mollard, Michel, Špacapan, Simon, Zemljič, Sara Sabrina
Format: Article
Language:English
Subjects:
Combinatorics
Fibonacci cube
Fibonacci numbers
Mathematics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Fibonacci cube of dimension n, denoted as Γn, is the subgraph of n-cube Qn induced by vertices with no consecutive 1’s. We study the maximum number of disjoint subgraphs in Γn isomorphic to Qk, and denote this number by qk(n). We prove several recursive results for qk(n), in particular we prove that qk(n)=qk−1(n−2)+qk(n−3). We also prove a closed formula in which qk(n) is given in terms of Fibonacci numbers, and finally we give the generating function for the sequence {qk(n)}n=0∞.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2015.03.016