Turán's problem and Ramsey numbers for trees

• Autorzy: Zhi-Hong Sun , Lin-Lin Wang , Yi-Li Wu
• Języki publikacji: EN

Abstrakty

EN

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V = {v₀,v₁,...,v_{n-1}}$, $E₁ = {v₀v₁,..., v₀v_{n-3},v_{n-4}v_{n-2},v_{n-3}v_{n-1}}$ and $E₂ = {v₀v₁,..., v₀v_{n-3},v_{n-3}v_{n-2},v_{n-3}v_{n-1}}$. For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r(Tₘ,Tₙ^i)$, where i ∈ {1,2} and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

Kategorie tematyczne

• 05C05: Trees
• 05C35: Extremal problems
• 05C55: Generalized Ramsey theory

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Colloquium Mathematicum
• Rocznik: 2015
• Tom: 139
• Numer: 2
• Strony: 273-298

Daty

wydano

2015

Twórcy

autor

Zhi-Hong Sun

• School of Mathematical Sciences, Huaiyin Normal University, Huaian, Jiangsu 223001, P.R. China

autor

Lin-Lin Wang

• School of Science, China University of Mining and Technology, Xuzhou, Jiangsu 221116, P.R. China

autor

Yi-Li Wu

• School of Mathematical Sciences, Huaiyin Normal University, Huaian, Jiangsu 223001, P.R. China

Identyfikatory

DOI

10.4064/cm139-2-8