Show simple item record

dc.contributor.advisorSands, G. William
dc.contributor.authorCurrie, James D.
dc.date.accessioned2005-07-21T21:28:50Z
dc.date.available2005-07-21T21:28:50Z
dc.date.issued1987
dc.identifier.citationCurrie, J. D. (1987). Non-repetitive walks in graphs and digraphs (Unpublished doctoral thesis). University of Calgary, Calgary, AB. doi:10.11575/PRISM/17416en_US
dc.identifier.isbn0315379715en
dc.identifier.urihttp://hdl.handle.net/1880/23624
dc.descriptionBibliography: p. 280-282.en
dc.description.abstractA 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.
dc.format.extentxxii, 323 leaves : ill. ; 30 cm.en
dc.language.isoeng
dc.rightsUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.
dc.subject.lccQA 166 C787 1988en
dc.subject.lcshGraph theory
dc.subject.lcshCombinatorial analysis
dc.titleNon-repetitive walks in graphs and digraphs
dc.typedoctoral thesis
dc.publisher.institutionUniversity of Calgaryen
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/17416
thesis.degree.nameDoctor of Philosophy (PhD)
thesis.degree.disciplineMathematics and Statistics
thesis.degree.grantorUniversity of Calgary
dc.identifier.lccQA 166 C787 1988en
dc.publisher.placeCalgaryen
ucalgary.thesis.notesoffsiteen
ucalgary.thesis.uarcreleaseyen
ucalgary.item.requestcopytrue
ucalgary.thesis.accessionTheses Collection 58.002:Box 612 215772215


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.