Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Path-fan Ramsey numbers

Share/Save/Bookmark

Salman, A.N.M. and Broersma, H.J. (2006) Path-fan Ramsey numbers. Discrete Applied Mathematics, 154 (9). pp. 1429-1436. ISSN 0166-218X

[img]PDF
Restricted to UT campus only: Request a copy
266Kb
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,F_m)$, where $P_n$ is a path on $n$ vertices and $F_m$ is the graph obtained from $m$ disjoint triangles by identifying precisely one vertex of every triangle ($F_m$ is the join of $K_1$ and $mK_2$). We determine the exact values of $R(P_n,F_m)$ for the following values of $n$ and $m$: $1\le n\le 5$ and $m \ge 2$; $n \ge 6$ and $2\le m \le (n+1)/2$; $6\le n\le 7$ and $m \ge n-1$; $n\ge 8$ and $n-1\le m\le n$ or $((q\cdot n-2q+1)/2\le m \le (q\cdot n-q+2)/2$ with $3\le q\le n-5)$ or $m\ge (n-3)^2/2$; odd $n\ge 9$ and $((q\cdot n-3q+1)/2 \le m\le (q\cdot n-2q)/2$ with $3\le q\le (n-3)/2)$ or $((q\cdot n-q-n+4)/2 \le m\le (q\cdot n-2q)/2$ with $(n-1)/2\le q\le n-5)$. Moreover, we give nontrivial lower bounds and upper bounds for $R(P_n,F_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/63661
Official URL:http://dx.doi.org/10.1016/j.dam.2005.05.040
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 237587