On Ramsey Numbers of Short Paths versus Large Wheels

Abstract

For two given graphs \(G_1\) and \(G_2\), the \({Ramsey\; number}\) \(R(G_1, G_2)\) is the smallest integer \(n\) such that for any graph \(G\) of order \(n\), either \(G\) contains \(G_1\) or the complement of \(G\) contains \(G_2\). Let \(P_n\) denote a path of order \(n\) and \(W_{m}\) a wheel of order \(m+1\). Chen et al. determined all values of \(R(P_n, W_{m})\) for \(n \geq m-1\). In this paper, we establish the best possible upper bound and determine some exact values for \(R(P_n, W_{m})\) with \(n \leq m-2\).