### 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.

Original language | Undefined |
---|---|

Title of host publication | 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization |

Editors | Haitze J. Broersma, U. Faigle, Johann L. Hurink, Stefan Pickl, Gerhard Woeginger |

Publisher | Elsevier |

Pages | 103-107 |

DOIs | |

Publication status | Published - 2003 |

Event | 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2003 - University of Twente, Enschede, Netherlands Duration: 14 May 2003 → 16 May 2003 |

### Publication series

Name | Electronic Notes in Discrete Mathematics |
---|---|

Publisher | Elsevier |

Volume | 13 |

### Workshop

Workshop | 2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2003 |
---|---|

Abbreviated title | CTW |

Country | Netherlands |

City | Enschede |

Period | 14/05/03 → 16/05/03 |

### Keywords

- Path
- IR-74946
- Fan
- Ramsey number

## Cite this

Salman, M. (2003). The Ramsey Numbers of Paths Versus Fans. In H. J. Broersma, U. Faigle, J. L. Hurink, S. Pickl, & G. Woeginger (Eds.),

*2nd Cologne-Twente Workshop on Graphs and Combinatorial Optimization*(pp. 103-107). (Electronic Notes in Discrete Mathematics; Vol. 13). Elsevier. https://doi.org/10.1016/S1571-0653(04)00448-2