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\le n \le 5$ and $m\ge 3$; $n\ge 6$ and ($m$ is odd, $3\le m\le 2n-1$) or ($m$ is even, $4\le m \le n+1$); $6\le n\le 7$ and $m=2n-2$ or $m \ge 2n$; $n\ge 8$ and $m=2n-2$ or $m=2n$ or ($q\cdot n-2q+1 \le m\le q\cdot n-q+2$ with $3\le q\le n-5$) or $m\ge (n-3)^2$; odd $n\ge 9$ and ($q\cdot n-3q+1\le m\le q\cdot n-2q$ with $3\le q\le (n-3)/2$) or ($q\cdot n-q-n+4m\le q\cdot n-2q$ with $(n-1)/2\le q\le 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$.
| Original language | English |
|---|---|
| Pages (from-to) | 1878-1884 |
| Number of pages | 7 |
| Journal | Discrete applied mathematics |
| Volume | 155 |
| Issue number | LNCS4549/14 |
| DOIs | |
| Publication status | Published - 1 Sept 2007 |
Fingerprint
Dive into the research topics of 'Path-kipas Ramsey numbers'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver