A Family of Partial Cubes with Minimal Fibonacci Dimension

A partial cube G is a graph that admits an isometric embedding into some hypercube Qk. This implies that vertices of G can be labeled with binary words of length k in a way that the distance between two vertices in the graph corresponds to the Hamming distance between their labels. The minimum k for which this embedding is possible is called the isometric dimension of G, denoted idim(G). A Fibonacci cube Γk is the partial cube obtained by deleting all the vertices in Qk whose labels contain word 11 as factor. It turns out that any partial cube can be always isometrically embedded also in a Fibonacci cube Γd. The minimum d is called the Fibonacci dimension of G, denoted fdim(G). In general, idim(G) ≤ fdim(G) ≤ 2 · idim(G) − 1. Despite there is a quadratic algorithm to compute the isometric dimension of a graph, the problem of checking, for a given G, whether idim(G) = fdim(G) is in general NP-complete. An important family of graphs for which this happens are the trees. We consider a kind of generalized Fibonacci cubes that were recently defined. They are the subgraphs of the hypercube Qk that include only vertices that avoid words in a given set S and are referred to as Qk(S). We prove some conditions on the words in S to obtain a family of partial cubes with minimal Fibonacci dimension equal to the isometric dimension.