On Ramsey numbers for paths versus wheels

Share/Save/Bookmark

Salman, A.N.M. and Broersma, H.J. (2007) On Ramsey numbers for paths versus wheels. Discrete Mathematics, 307 (7-8). pp. 975-982. ISSN 0012-365X

[img] PDF
Restricted to UT campus only
: Request a copy
410kB
Abstract:For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_n,W_m)$, where $P_n$ is a path on $n$ vertices and $W_m$ is the graph obtained from a cycle on $m$ vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of $R(P_n,W_m)$ for the following values of $n$ and $m: n=1,2,3$ or 5 and $m \ge 3$; $n=4$ and $m=3,4,5$ or 7; $n\ge 6$ and ($m$ is odd, $3 \le m \le 2n-1$) or ($m$ is even, $4\le m\le n+1$); odd $n\ge 7$ and $m=2n-2$ or $m=2n$ or $m \ge (n-3)^2$; odd $n\ge 9$ and $q\cdot n-2q+1 \le m \le q\cdot n-q+2$ with $3\le q \le n-5$. Moreover, we give nontrivial lower bounds and upper bounds for $R(P_n,W_m)$ for the other values of $m$ and $n$.

Item Type:Article
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/61767
Official URL:http://dx.doi.org/10.1016/j.disc.2005.11.049
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 241727