The Fibonacci dimension of a graph
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
The Fibonacci dimension ${\rm fdim}(G)$ of a graph $G$ is introduced as the smallest integer $f$ such that $G$ admits an isometric embedding into $\Gamma_f$, the $f$-dimensional Fibonacci cube. We give bounds on the Fibonacci dimension of a graph in terms of the isometric and lattice dimension, provide a combinatorial characterization of the Fibonacci dimension using properties of an associated graph, and establish the Fibonacci dimension for certain families of graphs. From the algorithmic point of view, we prove that it is NP-complete to decide whether ${\rm fdim}(G)$ equals the isometric dimension of $G$, and show that no algorithm to approximate ${\rm fdim}(G)$ has approximation ratio below $741/740$, unless P$=$NP. We also give a $(3/2)$-approximation algorithm for ${\rm fdim}(G)$ in the general case and a $(1+\varepsilon)$-approximation algorithm for simplex graphs.
Sergio Cabello; David Eppstein; Sandi Klavžar. The Fibonacci dimension of a graph. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/542
@article{10_37236_542,
author = {Sergio Cabello and David Eppstein and Sandi Klav\v{z}ar},
title = {The {Fibonacci} dimension of a graph},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/542},
zbl = {1217.05080},
url = {http://geodesic.mathdoc.fr/articles/10.37236/542/}
}
Cité par Sources :