Fibonacci dimension

The Fibonacci cube is, as its Wikipedia article says, a graph that is in many respects like a hypercube but with a Fibonacci number of vertices. Its vertices are binary strings with no two consecutive ones, and its edges link pairs of strings at Hamming distance one from each other. The Fibonacci cube formed from bitstrings of length \( d \) is an isometric subgraph of a \( d \)-dimensional hypercube (the graph of all length-\( d \) bitstrings), but it also contains as an isometric subgraph a hypercube of dimension \( \lceil d/2 \rceil \) (the binary strings in which only the bits in the even positions can be nonzero). Therefore, the graphs that can be isometrically embedded into Fibonacci cubes are the same as the ones that can be embedded into hypercubes, that is, the partial cubes.

A preprint I recently wrote on this subject with Sergio Cabello and Sandi Klavžar just came out on the arXiv (it's been on the IMFM preprint server for a little longer — if you're interested in graph theory, do check this link out, as it has over 1000 other papers, many of them on graphs). The idea is to investigate the lengths of the bitstrings needed to label a given graph so that graph distance equals Hamming distance and so that no label contains two consecutive ones. That is, we wish to embed graphs isometrically into Fibonacci cubes of minimum dimension. The problem turns out to be NP-hard — it is related to a version of the traveling salesman problem — but can solved exactly in some cases, such as 2d grid graphs. There are also some pretty good approximation algorithms, one of them based on lattice dimension, another based on the xkcd algorithm for traveling salesmen.

Comments: