Displaying similar documents to “Repetition thresholds for subdivided graphs and trees”

Repetition thresholds for subdivided graphs and trees

Pascal Ochem, Elise Vaslet (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -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.

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let  be the graph obtained from a given graph  by subdividing each edge  times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in (SODA 2002) 321–328], we prove that, for any graph , there exist graphs  with  edges that are Ramsey with respect to  .

Shape optimization problems for metric graphs

Giuseppe Buttazzo, Berardo Ruffini, Bozhidar Velichkov (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

): ∈ 𝒜, ℋ() = }, where ℋ ,,  }  ⊂ R . The cost functional ℰ() is the Dirichlet energy of defined through the Sobolev functions on vanishing on the points . We analyze the existence of a solution in both the families of connected sets and of metric graphs. At the end, several explicit examples are discussed.

Square-root rule of two-dimensional bandwidth problem

Lan Lin, Yixun Lin (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The bandwidth minimization problem is of significance in network communication and related areas. Let be a graph of vertices. The two-dimensional bandwidth () of is the minimum value of the maximum distance between adjacent vertices when is embedded into an  ×  grid in the plane. As a discrete optimization problem, determining () is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This...

Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong, Qinghui Liu (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The infinite Post Correspondence Problem (PCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [36 (2003) 231–245] showed that PCP is undecidable for domain alphabets of size 105, Halava and Harju [40 (2006) 551–557] showed that PCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that PCP is undecidable for domain alphabets of size 8.

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

For any finite word on a finite alphabet, we consider the basic parameters and of defined as follows: is the minimal natural number for which has no right special factor of length and is the minimal natural number for which has no repeated suffix of length . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words ...

Complexity of infinite words associated with beta-expansions

Christiane Frougny, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the complexity of the infinite word associated with the Rényi expansion of in an irrational base . When is the golden ratio, this is the well known Fibonacci word, which is Sturmian, and of complexity . For such that is finite we provide a simple description of the structure of special factors of the word . When =1 we show that . In the cases when or max} we show that the first difference of the complexity function takes value in for every , and consequently we determine...