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

DOI10.1016/J.DAM.2016.10.029MaRDI QIDQ505451zbMATH OpenOpenAlexFDO

Authors Michel Mollard

Publication date 23 January 2017

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

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

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)

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].

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

Cites work

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

Cited in

(12)

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