KAIST Discrete Math Seminar

The Fibonacci dimension fdim(G) of a graph G is introduced as the smallest integer f such that G admits an isometric embedding into the f-dimensional Fibonacci cube. We will see combinatorial relations between the Fibonacci dimension and the isometric or lattice dimension, and establish the Fibonacci dimension for certain families of graphs. Finally, we will discuss the problem of computing the Fibonacci dimension, namely, its NP-hardness and approximation algorithms.

Joint work with D. Eppstein and S. Klavžar. Manuscript available at arxiv:0903.2507.