JEDNOSTKA NAUKOWA KATEGORII A+

Turán's problem and Ramsey numbers for trees

Tom 139 / 2015

Zhi-Hong Sun, Lin-Lin Wang, Yi-Li Wu Colloquium Mathematicum 139 (2015), 273-298 MSC: 05C55, 05C35, 05C05. DOI: 10.4064/cm139-2-8

Streszczenie

Let $T_n^1=(V,E_1)$ and $T_n^2=(V,E_2)$ be the trees on $n$ vertices with $V=\{v_0,v_1,\ldots ,v_{n-1}\}$, $E_1=\{v_0v_1,\ldots ,v_0v_{n-3},v_{n-4}v_{n-2},v_{n-3}v_{n-1}\}$ and $E_2=\{v_0v_1,\ldots ,$ $v_0v_{n-3},v_{n-3}v_{n-2}, v_{n-3} v_{n-1}\}$. For $p\ge n\ge 5$ we obtain explicit formulas for ${\rm ex}(p;T_n^1)$ and ${\rm ex}(p;T_n^2)$, where ${\rm ex}(p;L)$ denotes the maximal number of edges in a graph of order $p$ not containing $L$ as a subgraph. Let $r(G_ 1, G_ 2)$ be the Ramsey number of the two graphs $G_1$ and $G_2$. We also obtain some explicit formulas for $r(T_m,T_n^i)$, where $i\in \{1,2\}$ and $T_m$ is a tree on $m$ vertices with $\varDelta (T_m)\le m-3$.

Autorzy

  • Zhi-Hong SunSchool of Mathematical Sciences
    Huaiyin Normal University
    Huaian, Jiangsu 223001, P.R. China
    e-mail
  • Lin-Lin WangSchool of Science
    China University of Mining and Technology
    Xuzhou, Jiangsu 221116, P.R. China
    e-mail
  • Yi-Li WuSchool of Mathematical Sciences
    Huaiyin Normal University
    Huaian, Jiangsu 223001, P.R. China
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek