Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes

DOI10.1016/J.DAM.2016.10.029zbMATH Open1354.05088arXiv1606.00138OpenAlexW2413494309MaRDI QIDQ505451FDOQ505451

Authors: Michel Mollard 

Publication date: 23 January 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The Fibonacci cube of dimension n, denoted as $Gamma$ n , is the subgraph of n-cube Q n induced by vertices with no consecutive 1's. In this short note we prove that asymptotically all vertices of $Gamma$ n are covered by a maximum set of disjoint subgraphs isomorphic to Q k , answering an open problem proposed in [2].

Full work available at URL: https://arxiv.org/abs/1606.00138

Recommendations

• On disjoint hypercubes in Fibonacci cubes
• Counting disjoint hypercubes in Fibonacci cubes
• Maximal hypercubes in Fibonacci and Lucas cubes
• Generalized Fibonacci cubes
• The Fibonacci hypercube

zbMATH Keywords

Fibonacci numbersFibonacci cube

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Cites Work

• On disjoint hypercubes in Fibonacci cubes
• Counting disjoint hypercubes in Fibonacci cubes

Cited In (12)

• On the chromatic polynomial and the domination number of \(k\)-Fibonacci cubes
• Daisy cubes and distance cube polynomial
• Boundary enumerator polynomial of hypercubes in Fibonacci cubes
• On the irregularity of \(\pi \)-permutation graphs, Fibonacci cubes, and trees
• Fibonacci-run graphs. II: Degree sequences
• Counting disjoint hypercubes in Fibonacci cubes
• Fibonacci-run graphs. I: Basic properties
• \(k\)-Fibonacci cubes: a family of subgraphs of Fibonacci cubes
• On the domination number and the total domination number of Fibonacci cubes
• The structure of \(k\)-Lucas cubes
• On disjoint hypercubes in Fibonacci cubes
• Some diameter notions of Fibonacci cubes

This page was built for publication: Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q505451)