# The Ramsey Numbers of Paths Versus Fans

Salman, A.N.M.
and
Broersma, H.J.
(2003)
*The Ramsey Numbers of Paths Versus Fans.*
In:
Hajo Broersma
&
Ulrich Faigle
&
Johann Hurink
&
Stefan Pickl
&
Gerhard Woeginger
(Eds.),
2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization.
Electronic Notes in Discrete Mathematics, 13
.
Elsevier, pp. 103-107.

PDF
Restricted to UT campus only 346kB |

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(Pn,Fm), where Pn is a path on n vertices and Fm is the graph obtained from m disjoint triangles by identifying precisely one vertex of every triangle (Fm is the join of K1 and mK2). We determine exact values for R(Pn,Fm) for the following values of n and m: n = 1,2 or 3 and m ≥ 2; n ≥ 4 and 2 ≤ m ≤ (n + 1)/2; n ≥ 7 and m = n − 1 or m = n; n ≥ 8 and (k · n − 2k + 1)/2 ≤ m ≤ (k · n − k + 2)/2 with 3 ≤ k ≤ n − 5; n = 4,5 or 6 and m ≥ n − 1; n ≥ 7 and m ≥ (n − 3)2/2. |

Item Type: | Book Section |

Copyright: | © 2003 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/74946 |

Official URL: | http://dx.doi.org/10.1016/S1571-0653(04)00448-2 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page