Non-repetitive walks in graphs and digraphs
Date
1987
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A word w over alphabet z is non-repetitive if we cannot write w = abbc; a, b, c e X * , b e. That is, no subword of w appears twice in a row in w. In 1906, Axel Thue, the Norwegian number theorist, showed that arbitrarily long non-repetitive words exist on a three letter alphabet. Call graph or digraph G versatile if arbitrarily long non-repetitive words can be walked on G. This work deals with two questions: (1) Which graphs are versatile? (2) Which digraphs are versatile? Our results concerning versatility of digraphs may be considered to give information about the structure of non-repetitive words on finite alphabets. We attack these questions as follows: (I) We introduce a partial ordering of digraphs called mimicking. We show that if digraph G mimics digraph H, then if His versatile, so is G. (II) We then produce two sets of digraphs MIN and MAX, and show that every digraph of MIN is versatile ( These digraphs are intended to be minimal in the mimicking partial order with respect to being versatile. ) and no digraph of MAX is versatile. ( The digraphs of MAX are intended to be maximal with respect to not being versatile. (III) In a lengthy classification, we show that every digraph either mimics a digraph of MIN, and hence is versatile, or "reduces" to some digraph mimicked by a digraph of MAX, and hence is not versatile. We conclude that a digraph is versatile exactly when it mimics one of the digraphs in the finite set MIN. The set MIN cont~ins eighty-nine ( 89 ) digraphs, and the set MAX contains twenty-five ( 25 ) individual digraphs, and one infinite family of digraphs.
Description
Bibliography: p. 280-282.
Keywords
Citation
Currie, J. D. (1987). Non-repetitive walks in graphs and digraphs (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/17416