On the Ramsey number for paths and beaded wheels

Kashif Ali
Faculty of Mathematics, COMSATS Institute of Information Technology, Lahore, Pakistan.
Edy Tri Baskoro
Combinatorial Mathematics Research Division, Faculty of Mathematics and Natural
Sciences, Institut Teknologi Bandung Jalan Genesha, Bandung, Indonesia.
Ioan Tomescu
Faculty of Mathematics and Computer Sciences, University of Bucharest, Bucharest, Romania.

\(^{1}\)Corresponding Author: kashif.ali@ciitlahore.edu.pk

Copyright © 2009 Kashif Ali, Edy Tri Baskoro, Ioan Tomescu. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Published: December, 2009.

Abstract

For given graphs \(G\) and \(H\), the Ramsey number \(R(G, H)\) is the least natural number n such that for every graph \(F\) of order \(n\) the following condition holds: either \(F\) contains \(G\) or the complement of \(F\) contains \(H\). Beaded wheel \(BW_{2,m}\) is a graph of order \(2m + 1\) which is obtained by inserting a new vertex in each spoke of the wheel \(W_m\). In this paper, we determine the Ramsey number of paths versus Beaded wheels: \(R(P_n, BW_{2,m}) = 2n − 1\) or \(2n\) if \(m ≥ 3\) is even or odd, respectively, provided \(n ≥ 2m^2 − 5m + 4\).

Keywords:

Ramsey number, path, beaded wheel.