Displaying similar documents to “A note on the Size-Ramsey number of long subdivisions of graphs”

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.

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.

Repetition thresholds for subdivided graphs and trees

Pascal Ochem, Elise Vaslet (2012)

RAIRO - Theoretical Informatics and 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.

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...

On the number of dissimilar pfaffian orientations of graphs

Marcelo H. de Carvalho, Cláudio L. Lucchesi, U. S.R. Murty (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A subgraph of a graph is if has a perfect matching. An orientation of is if, for every conformal even circuit , the number of edges of whose directions in  agree with any prescribed sense of orientation of is odd. A graph is if it has a Pfaffian orientation. Not every graph is Pfaffian. However, if has a Pfaffian orientation , then the determinant of the adjacency matrix of is the square of the number of perfect matchings of . (See the book by Lovász and Plummer [. Annals...

Hereditary properties of words

József Balogh, Béla Bollobás (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let be a hereditary property of words, , an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every  or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most ⌈( + 1)/2⌉⌈( + 1)/2⌈...