\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Sergio Cabello, David Eppstein and Sandi Klav{\v z}ar}
%
%
\medskip
\noindent
%
%
{\bf The Fibonacci Dimension of a Graph}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.
\end{document}