Repetition Thresholds for Subdivided Graphs and Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles RAIRO - Theoretical Informatics and Applications (RAIRO: ITA) Year : 2012

Repetition Thresholds for Subdivided Graphs and Trees

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.

Dates and versions

lirmm-00739384 , version 1 (08-10-2012)

Identifiers

Cite

Pascal Ochem, Elise Vaslet. Repetition Thresholds for Subdivided Graphs and Trees. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), 2012, 46 (1), pp.123-130. ⟨10.1051/ita/2011122⟩. ⟨lirmm-00739384⟩
107 View
0 Download

Altmetric

Share

More