Now showing items 27-40 of 40

• #### The metric dimension and metric independence of a graph ﻿

(The Charles Babbage Research Centre, 2001)
A vertex x of a graph G resolves two vertices u and v of G if the distance from x to u does not equal the distance from x to v. A set S of vertices of G is a resolving set for G if every two distinct vertices of G are ...
• #### Non repetitive walks in graphs and digraphs ﻿

(The University of CalgaryUniversity of Calgary, 1987-06)
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 ...
• #### Non-Repetitive Tilings ﻿

(The Electronic Journal of Combinatorics, 2002-07-03)
In 1906 Axel Thue showed how to construct an infinite non-repetitive (or square-free) word on an alphabet of size 3. Since then this result has been rediscovered many times and extended in many ways. We present a two-dimensional ...
• #### A Note on Antichains of Words ﻿

(The Electronic Journal of Combinatorics, 1995-10-14)
We can compress the word 'banana' as xyyz, where x= 'b', y= 'an',z= 'a'. We say that 'banana' encounters yy. Thus a 'coded' version of yy shows up in 'banana'. The relation 'u encounters w' is transitive, and thus generates ...
• #### The number of order–preserving maps of fences and crowns ﻿

(Springer, 1991-06)
We perform an exact enumeration of the order-preserving maps of fences (zig-zags) and crowns (cycles). From this we derive asymptotic results.
• #### The Number of Ternary Words Avoiding Abelian Cubes Grows Exponentially ﻿

(2004-06-19)
We show that the number of ternary words of length n avoiding abelian cubes grows faster than r^n, where r = 2^{1/24}
• #### On avoidability of formulas with reversal ﻿

(EDP Sciences, 2018-02-13)
While a characterization of unavoidable formulas (without reversal) is well-known, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas ...
• #### Square-free Words with Square-free Self-shuffles ﻿

(The Electronic Journal of Combinatorics, 2014-01-12)
We answer a question of Harju: For every n ≥ 3 there is a square-free ternary word of length n with a square-free self-shuffle.
• #### Suffix conjugates for a class of morphic subshifts ﻿

(Cambridge University Press, 2015-09)
Let A be a finite alphabet and f: A^* --> A^* be a morphism with an iterative fixed point f^\omega(\alpha), where \alpha{} is in A. Consider the subshift (X, T), where X is the shift orbit closure of f^\omega(\alpha) and ...
• #### A Ternary Square-free Sequence Avoiding Factors Equivalent to abcacba ﻿

(The Electronic Journal of Combinatorics, 2016-05-27)
We solve a problem of Petrova, finalizing the classification of letter patterns avoidable by ternary square-free words; we show that there is a ternary square-free word avoiding letter pattern xyzxzyx. In fact, we characterize ...
• #### There are Ternary Circular Square-Free Words of Length n for n ≥ 18 ﻿

(The Electronic Journal of Combinatorics, 2002-10-11)
There are circular square-free words of length n on three symbols for n≥18. This proves a conjecture of R. J. Simpson.
• #### There Exist Binary Circular 5/2+ Power Free Words of Every Length ﻿

(The Electronic Journal of Combinatorics, 2004-01-23)
We show that there exist binary circular 5/2+ power free words of every length.
• #### Unary patterns under permutations ﻿

(Elsevier, 2018-06-04)
Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, ...
• #### Words without Near-Repetitions ﻿

(Canadian Mathematical Society, 1992-06-01)
We find an infinite word w on four symbols with the following property: Two occurrences of any block in w must be separated by more than the length of the block. That is, in any subword of w of the form xyx, the length of ...