Abstract of Paper

Embedding Fibonacci Cubes into Hypercubes with $\Omega(2^{cn})$ Faulty Nodes
by Rostislav Caha and Petr Gregor

Abstract:

Fibonacci Cubes are special subgraphs of hypercubes based on Fibonacci
numbers. We present a construction of a direct embedding of a Fibonacci Cube
of dimension n into a faulty hypercube of dimension n with less or equal
$2^{\lceil\frac {n}{4}\rceil -1}$ faults. In fact, there exists a direct
embedding of a Fibonacci Cube of dimension n into faulty hypercube of
dimension n with at most $\frac{2^n}{4f_n}$ faults ($f_n$ is the n-th
Fibonacci number). Thus the number $\phi(n)$ of tolerable faults grows
exponentially with respect to a dimension n, $\phi(n)=\Omega (2^{cn})$, for
$c=2 - \log_{2}(1+\sqrt 5) \doteq 0.31$.  On the other hand, $\phi (n)=O(2^{dn})$, for $d=(8-3\log_{2}3)/4\doteq 0.82$.  As a corollary, there
exists a nearly polynomial algorithm constructing a direct embedding of a
Fibonacci Cube of dimension n into a faulty hypercube of dimension n (if it
exists) provided that faults are given on input by enumeration. However, the
problem is NP-complete, if faults are given on input with an asterisk
convention.