Ramsey Number of Wheels Versus Cycles and Trees

Canadian mathematical bulletin

Ghaffar Raeisi¹  Ali Zaghian² 

[1] Department of Mathematical Sciences, Shahrekord University, Shahrekord, P.O. Box 115, Iran;Department of Mathematics and Cryptography, Malek-Ashtar University of Technology, Isfahan, P.O. Box 83145/115, Iran

关键词: Ramsey number;    wheel;    tree;    cycle;   

DOI  :  10.4153/CMB-2015-057-5

学科分类：数学（综合）

来源: University of Toronto Press * Journals Division

【 摘 要 】

Let $G_1, G_2, dots , G_t$ be arbitrary graphs. TheRamsey number $R(G_1, G_2, dots, G_t)$ is the smallest positiveinteger $n$ such that if the edges of the complete graph $K_n$arepartitioned into $t$ disjoint color classes giving $t$ graphs$H_1,H_2,dots,H_t$, then at least one $H_i$ has a subgraphisomorphic to $G_i$. In this paper, we provide the exact valueofthe $R(T_n,W_m)$ for odd $m$, $ngeq m-1$, where $T_n$ iseither a caterpillar, a tree with diameter at most four or atreewith a vertex adjacent to at least $lceilfrac{n}{2}ceil-2$ leaves. Also, wedetermine $R(C_n,W_m)$ for even integers $n$ and $m$, $ngeqm+500$, which improves a result of Shi and confirms aconjecture of Surahmat et al. In addition, the multicolor Ramseynumber of treesversus an odd wheel is discussed in this paper.

【 授权许可】

Unknown