Sergio Cabello, The Fibonacci dimension of a graph

The Fibonacci dimension of a graph
Sergio Cabello
Dept. of Mathematics, University of Ljubljana, Slovenia
2010/2/10 Wed, 4PM-5PM

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.


Comments are closed.