A k-ary n-cube is a graph with kn vertices, each associated to a word of length n over an alphabet of cardinality k. The subgraph obtained deleting those vertices which contain a given k-ary word f as a factor is here introduced and called the k-ary n-cube avoiding f. When, for any n, such a subgraph is isometric to the cube, the word f is said isometric. In the binary case, isometric words can be equivalently defined, independently from hypercubes. A binary word f is isometric if and only if it is good, i.e., for any pair of f-free words u and v, u can be transformed in v by exchanging one by one the bits on which they differ and generating only f-free words. These two approaches are here considered in the case of a k-ary alphabet, showing that they are still coincident for k= 3, but they are not from k= 4 on. Bad words are then characterized in terms of their overlaps with errors. Further properties are obtained on non-isometric words and their index, in the case of a quaternary alphabet.

Quaternary n-cubes and Isometric Words

Anselmo M.;Flores M.;
2021-01-01

Abstract

A k-ary n-cube is a graph with kn vertices, each associated to a word of length n over an alphabet of cardinality k. The subgraph obtained deleting those vertices which contain a given k-ary word f as a factor is here introduced and called the k-ary n-cube avoiding f. When, for any n, such a subgraph is isometric to the cube, the word f is said isometric. In the binary case, isometric words can be equivalently defined, independently from hypercubes. A binary word f is isometric if and only if it is good, i.e., for any pair of f-free words u and v, u can be transformed in v by exchanging one by one the bits on which they differ and generating only f-free words. These two approaches are here considered in the case of a k-ary alphabet, showing that they are still coincident for k= 3, but they are not from k= 4 on. Bad words are then characterized in terms of their overlaps with errors. Further properties are obtained on non-isometric words and their index, in the case of a quaternary alphabet.
2021
9783030850876
9783030850883
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4770130
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 125
  • ???jsp.display-item.citation.isi??? ND
social impact