Repetition Thresholds for Subdivided Graphs and Trees

Pascal Ochem 1 Elise Vaslet 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and "large enough" subdivisions of graphs for every alphabet size.
Type de document :
Article dans une revue
RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2012, 46 (1), pp.123-130
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00739384
Contributeur : Pascal Ochem <>
Soumis le : lundi 8 octobre 2012 - 10:30:02
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00739384, version 1

Citation

Pascal Ochem, Elise Vaslet. Repetition Thresholds for Subdivided Graphs and Trees. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2012, 46 (1), pp.123-130. 〈lirmm-00739384〉

Partager

Métriques

Consultations de la notice

127