UC Irvine

The Fibonacci dimension 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 fdim(G) equals the isometric dimension of G, and show that no algorithm to approximate fdim(G) has approximation ratio below 741/740, unless P=NP. We also give a (3/2)-approximation algorithm for fdim(G) in the general case and a (1+epsilon)-approximation algorithm for simplex graphs.