Geodesic
On ternary square-free circular words
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Circular words are cyclically ordered finite sequences of letters. We give a computer-free proof of the following result by Currie: square-free circular words over the ternary alphabet exist for all lengths $l$ except for 5, 7, 9, 10, 14, and 17. Our proof reveals an interesting connection between ternary square-free circular words and closed walks in the $K_{3{,}3}$ graph. In addition, our proof implies an exponential lower bound on the number of such circular words of length $l$ and allows one to list all lengths $l$ for which such a circular word is unique up to isomorphism.
DOI : 10.37236/412
Classification : 68R15, 05C38
Mots-clés : cyclically ordered finite sequences 
@article{10_37236_412,
     author = {Arseny M. Shur},
     title = {On ternary square-free circular words},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/412},
     zbl = {1213.68480},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/412/}
}
TY  - JOUR
AU  - Arseny M. Shur
TI  - On ternary square-free circular words
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/412/
DO  - 10.37236/412
ID  - 10_37236_412
ER  - 
%0 Journal Article
%A Arseny M. Shur
%T On ternary square-free circular words
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/412/
%R 10.37236/412
%F 10_37236_412
Arseny M. Shur. On ternary square-free circular words. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/412

Cité par Sources :