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.
Anselmo, M., Giammarresi, D., Madonia, M., Mantaci, S. (2025). Partial Cubes and Fibonacci Dimension: Insights and Perspectives. In S.K. Ko, F. Manea (a cura di), Developments in Language Theory 29th International Conference, DLT 2025, Seoul, South Korea, August 19–22, 2025, Proceedings (pp. 15-29). GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND : SPRINGER INTERNATIONAL PUBLISHING AG [10.1007/978-3-032-01475-7_2].
Partial Cubes and Fibonacci Dimension: Insights and Perspectives
Mantaci S.
2025-01-01
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
KoreaDLT2025.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
1.54 MB
Formato
Adobe PDF
|
1.54 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
