dc.contributor.author Currie, James Daniel dc.date.accessioned 2019-04-10T17:53:43Z dc.date.available 2019-04-10T17:53:43Z dc.date.issued 1987-06 dc.identifier.citation Currie, James Daniel. Non repetitive walks in graphs and digraphs; A Thesis submitted to the Faculty of Graduate Studies in partial fulfillment of the requirement for the degree of Doctor of Philosophy, Department of Mathematics and Statistics, University of Calgary. Calgary, Alberta, June 1987. dc.identifier.uri http://hdl.handle.net/10680/1654 dc.description PhD thesis of James Daniel Currie (University of Calgary, 1987) en_US dc.description.abstract A word $w$ over alphabet $\Sigma$ is {\em non-repetitive} if we cannot write $w=abbc$, $a,b,c\in\Sigma^*$, $b\ne\epsilon$. 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. en_US Call a graph or digraph $G$ {\em versatile} if arbitrarily long non-repetitive words can be walked on $G$. This work deals with two questions: \begin{enumerate} \item Which graphs are versatile? \item Which digraphs are versatile? \end{enumerate} 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: \begin{enumerate} \item We introduce a partial order on digraphs called {\em mimicking}. We show that if digraph $G$ mimics digraph $H$, then if $H$ is versatile, so is $G$. \item 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.) \item 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 contains eighty-nine (89) digraphs, and the set MAX contains twenty-five (25) individual digraphs, and one infinite family of digraphs. \end{enumerate} dc.language.iso en en_US dc.publisher The University of Calgary en_US dc.rights info:eu-repo/semantics/openAccess en_US dc.subject combinatorics on words, non-repetitive words, square-free words, words walked on graphs en_US dc.title Non repetitive walks in graphs and digraphs en_US dc.type Thesis en_US dc.description.degree Doctor of Philosophy, Department of Mathematics and Statistics dc.publisher.grantor University of Calgary
﻿