Partial Cubes and Fibonacci Dimension: Insights and Perspectives

Abstract

A partial cube is a graph.G that can be isometrically embedded into a hypercube.Q(k), with the minimum of such k called the isometric dimension,.idim(G), of.G. A Fibonacci cube Gamma(k) excludes strings containing 11 from the vertices. Any partial cube.G embeds into some Gamma(d), defining Fibonacci dimension,.fdim(G), as the minimum of such d.It holds.idim(G) <= fdim(G) <= 2 center dot idim(G) - 1. While.idim(G) is computable in polynomial time, check whether.idim(G) = fdim(G) is NP-complete. We survey the properties of partial cubes and Generalized Fibonacci Cubes and present a new family of graphs.G for which.idim(G) = fdim(G). We conclude with some open problems.