Path-kipas Ramsey numbers


Salman, A.N.M. and Broersma, H.J. (2004) Path-kipas Ramsey numbers. [Report]

open access
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,\hat{K}_m)$, where $P_n$ is a path on $n$ vertices and $\hat{K}_m$ is the graph obtained from the join of $K_{1}$ and $P_{m}$. We determine the exact values of $R(P_n,\hat{K}_m)$ for the following values of $n$ and $m$: $1\leq n\leq 5$ and $m\geq 3$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); $6\le n\le7$ and $m=2n-2$ or $m\geq 2n$; $n\geq8$ and $m=2n-2$ or $m=2n$ or $(q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5)$ or $m\geq (n-3)^2$; odd $n\geq9$ and $(q\cdot n-3q+1\leq m\leq q\cdot n-2q$ with $3\leq q\leq (n-3)/2)$ or $(q\cdot n-q-n+4\leq m\leq q\cdot n-2q$ with $(n-1)/2\leq q\leq n-4)$. Moreover, we give lower bounds and upper bounds for $R(P_{n},\hat{K}_m)$ for the other values of $m$ and $n$.
Item Type:Report
Additional information:Imported from MEMORANDA
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 220232