Generalized Fibonacci Cubes Based on Swap and Mismatch Distance

Abstract

The hypercube of dimension n is the graph with 2n 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.