Quaternary n-cubes and Isometric Words

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.