Isometric Sets of Words and Generalizations of the Fibonacci Cubes

Abstract

The hypercube Q(n) is a graph whose 2(n) 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 Q(n)(f) is defined by selecting all vertices not containing f as a factor. A word f is said to be isometric if Q(n)(f) is an isometric subgraph of Q(n), i.e., keeping the distances between the remaining nodes. Graphs Q(n)(f) were defined and studied as a generalization of Fibonacci cubes Q(n)(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.