Ramsey numbers for the pair sparse graph-path or cycle

Abstract:

Let $G$ be a connected graph on $n$ vertices with no more than $n(1 + \varepsilon )$ edges, and ${P_k}$ or ${C_k}$ a path or cycle with $k$ vertices. In this paper we will show that if $n$ is sufficiently large and $\varepsilon$ is sufficiently small then for $k$ odd \[ r(G, {C_k}) = 2n - 1.\] Also, for $k \geqslant 2$, \[ r(G, {P_k}) = \max \{ n + [k/2] - 1, n + k - 2 - \alpha \prime - \delta \} ,\] where $\alpha \prime$ is the independence number of an appropriate subgraph of $G$ and $\delta$ is $0$ or $1$ depending upon $n$, $k$ and $\alpha \prime$.