2026-08-05T08:38:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23104 2025-10-02T12:37:39Z ddc:004 open_access

A Family of Partial Cubes with Minimal Fibonacci Dimension Anselmo, Marcella Castiglione, Giuseppa Flores, Manuela Giammarresi, Dora Madonia, Maria Mantaci, Sabrina Isometric sets of words Hypercubes Partial cubes Isometric dimension Generalized Fibonacci Cubes A partial cube G is a graph that admits an isometric embedding into some hypercube Q_k. 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 Q_k 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 Q_k that include only vertices that avoid words in a given set S and are referred to as Q_k(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marcella Anselmo and Giuseppa Castiglione and Manuela Flores and Dora Giammarresi and Maria Madonia and Sabrina Mantaci 2025 Is Part Of LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2025.10 urn:nbn:de:0030-drops-231044 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode