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.
Anselmo, M., Castiglione, G., Flores, M., Giammarresi, D., Madonia, M., Mantaci, S. (2024). Isometric Sets of Words and Generalizations of the Fibonacci Cubes. ??????? it.cilea.surplus.oa.citation.tipologie.CitationProceedings.prensentedAt ??????? Twenty Years of Theoretical and Practical Synergies : 20th Conference on Computability in Europe, CiE 2024, Amsterdam, The Netherlands, [10.1007/978-3-031-64309-5_35].
Isometric Sets of Words and Generalizations of the Fibonacci Cubes
Giammarresi D.;
2024-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
