** AUTHORS**: M. Anselmo, G.Castiglione, M. Flores, D. Giammarresi, M. Madonia, S. Mantaci

* URL*: https://link.springer.com/chapter/10.1007/978-3-031-34326-1_2

**Work Package** : Work Package 7 – REVER

**Keywords**: Swap and mismatch distance, Isometric words, Hypercube

**Abstract**

The hypercube of dimension *n* is the graph whose vertices are the 2^{n}binary words of length *n*, and there is an edge between two of them if they have Hamming distance 1. We consider an edit distance based on swaps and mismatches, to which we refer as *tilde-distance*, and define the *tilde-hypercube* with edges linking words at tilde-distance 1. Then, we introduce and study some isometric subgraphs of the tilde-hypercube obtained by using special words called *tilde-isometric words*. The subgraphs keep only the vertices that avoid a given tilde-isometric word as a factor. An infinite family of tilde-isometric words is described; they are isometric with respect to the tilde-distance, but not to the Hamming distance. In the case of word 11, the subgraph is called *tilde-Fibonacci cube*, as a generalization of the classical Fibonacci cube. The tilde-hypercube and the tilde-Fibonacci cube can be recursively defined; the same holds for the number of their edges. This allows an asymptotic estimation of the number of edges in the tilde-Fibonacci cube, in comparison to the total number in the tilde-hypercube.