2026-07-25T22:07:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23804 2026-02-09T06:17:13Z ddc:004 open_access

Generalized Fibonacci Cubes Based on Swap and Mismatch Distance Anselmo, Marcella Castiglione, Giuseppa Flores, Manuela Giammarresi, Dora Madonia, Maria Mantaci, Sabrina Swap and mismatch distance Isometric words Hypercube The hypercube of dimension n is the graph with 2ⁿ vertices associated to all binary words of length n and edges connecting pairs of vertices with Hamming distance equal to 1. Here, an edit distance based on swaps and mismatches is considered and referred to as tilde-distance. Accordingly, the tilde-hypercube is defined, with edges linking words having tilde-distance equal to 1. The focus is on the subgraphs of the tilde-hypercube obtained by removing all vertices having a given word as factor. If the word is 11, then the subgraph is called tilde-Fibonacci cube; in the case of a generic word, it is called generalized tilde-Fibonacci cube. The paper surveys recent results on the definition and characterization of those words that define generalized tilde-Fibonacci cubes that are isometric subgraphs of the tilde-hypercube. Finally, a special attention is given to the study of the tilde-Fibonacci cubes. 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 OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Grossi.5 urn:nbn:de:0030-drops-238044 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.5 eng https://creativecommons.org/licenses/by/4.0/legalcode