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.