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. (2003) Path-fan Ramsey numbers. [Report]

[img]
Preview
PDF
571Kb
Abstract:For two given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $p$ such that for every graph $F$ on $p$ vertices the following holds: either $F$ contains $G$ as a subgraph or the complement of $F$ 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 exact values for $R(P_{n},F_{m})$ for the following values of $n$ and $m$: $n=1,2$ or $3$ and $m\geq 2$; $n\geq 4$ and $2\leq m\leq (n+1)/2$; $n\geq7$ and $m=n-1$ or $m=n$; $n\geq 8$ and $(k\cdot n-2k+1)/2\leq m\leq (k\cdot n-k+2)/2$ with $3\leq k\leq n-5$; $n=4,5$ or $6$ and $m\geq n-1$; $n\geq 7$ and $m\geq (n-3)^2/2$. We conjecture that $R(P_{n},F_{m}) \leq 2m+n-3$ for the other values of $m$ and $n$.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65888
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page