Isometric Sets of Words and Generalizations of the Fibonacci Cubes

AUTHORS: Marcella Anselmo Giuseppa Castiglione Manuela Flores, Dora Giammarresi,

Maria Madonia Sabrina Mantaci 

WORK PACKAGE: WP 7 – REVER

URL https://link.springer.com/chapter/10.1007/978-3-031-64309-5_35

Keywords: Isometric sets of words Hamming distance Hypercubes Generalized Fibonacci Cubes

Abstract
The hypercube Qn is a graph whose 2n vertices can be associated to all binary words of length n in a way that adjacent vertices get words that differ only in one symbol. Given a word f, the subgraph Qn(f) is defined by selecting all vertices not containing f as a factor. A word f is said to be isometric if Qn(f) is an isometric subgraph of Qn, i.e., keeping the distances between the remaining nodes. Graphs Qn(f) were defined and studied as a generalization of Fibonacci cubes Qn(11). Isometric words have been completely characterized using combinatorial methods for strings.

We introduce the notion of isometric sets of words with the aim of capturing further interesting cases in the scenario of isometric subgraphs of the hypercubes. We prove some combinatorial properties and study special interesting cases.