A partial cube is a graph G that can be isometrically embedded into a hypercube Qk, with the minimum of such k called the isometric dimension, idim(G), of G. A Fibonacci cubeΓk excludes strings containing 11 from the vertices. Any partial cube G embeds into some Γd, defining Fibonacci dimension, fdim(G), as the minimum of such d. It holds idim(G)≤fdim(G)≤2·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.
Anselmo, M., Giammarresi, D., Madonia, M., Mantaci, S. (2026). Partial Cubes and Fibonacci Dimension: Insights and Perspectives. In Developments in Language Theory (pp.15-29). Springer [10.1007/978-3-032-01475-7_2].
Partial Cubes and Fibonacci Dimension: Insights and Perspectives
Giammarresi, Dora
;
2026-01-01
Abstract
A partial cube is a graph G that can be isometrically embedded into a hypercube Qk, with the minimum of such k called the isometric dimension, idim(G), of G. A Fibonacci cubeΓk excludes strings containing 11 from the vertices. Any partial cube G embeds into some Γd, defining Fibonacci dimension, fdim(G), as the minimum of such d. It holds idim(G)≤fdim(G)≤2·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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
