Counting disjoint hypercubes in Fibonacci cubes

Saygı E., Eğecioğlu O.

DISCRETE APPLIED MATHEMATICS, vol.215, pp.231-237, 2016 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 215
  • Publication Date: 2016
  • Doi Number: 10.1016/j.dam.2016.07.004
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.231-237
  • Hacettepe University Affiliated: Yes


We provide explicit formulas for the maximum number q(k)(n) of disjoint subgraphs isomorphic to the k-dimensional hypercube in the n-dimensional Fibonacci cube Gamma(n), for small k, and prove that the limit of the ratio of such cubes to the number of vertices in Gamma(n), is 1/2(k) for arbitrary k. This settles a conjecture of Gravier, Mollard, Spacapan and Zemljic about file limiting behavior of q(k)(n). (C) 2016 Elsevier B.V. All rights reserved.