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 2nbinary 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.