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.
Partial Cubes and Fibonacci Dimension: Insights and Perspectives
Anselmo, Marcella;
2026
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
