Geodesic
On ternary square-free circular words
The electronic journal of combinatorics, Tome 17 (2010)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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 
Arseny M. Shur. On ternary square-free circular words. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/412
@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

Cité par Sources :