International Journal of Combinatorics
Volume 2011 (2011), Article ID 649687, 9 pages
http://dx.doi.org/10.1155/2011/649687
Research Article

Ramsey Numbers for Theta Graphs

M. M. M. Jaradat,1,2 M. S. A. Bataineh,1 and S. M. E. Radaideh1

1Department of Mathematics, Yarmouk University, Irbid 21163, Jordan
2Department of Mathematics, Statistics, and Physics, Qatar University, Doha, Qatar

Received 14 January 2011; Revised 27 March 2011; Accepted 31 March 2011

Academic Editor: Alois Panholzer

Copyright © 2011 M. M. M. Jaradat et al. 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.

Abstract

The graph Ramsey number 𝑅 ( 𝐹 1 , 𝐹 2 ) is the smallest integer 𝑁 with the property that any complete graph of at least 𝑁 vertices whose edges are colored with two colors (say, red and blue) contains either a subgraph isomorphic to 𝐹 1 all of whose edges are red or a subgraph isomorphic to 𝐹 2 all of whose edges are blue. In this paper, we consider the Ramsey numbers for theta graphs. We determine 𝑅 ( 𝜃 4 , 𝜃 𝑘 ) , 𝑅 ( 𝜃 5 , 𝜃 𝑘 ) for 𝑘 ≥ 4 . More specifically, we establish that 𝑅 ( 𝜃 4 , 𝜃 𝑘 ) = 𝑅 ( 𝜃 5 , 𝜃 𝑘 ) = 2 𝑘 − 1 for 𝑘 ≥ 7 . Furthermore, we determine 𝑅 ( 𝜃 𝑛 , 𝜃 𝑛 ) for 𝑛 ≥ 5 . In fact, we establish that 𝑅 ( 𝜃 𝑛 , 𝜃 𝑛 ) = ( 3 𝑛 / 2 ) − 1 if 𝑛 is even, 2 𝑛 − 1 if 𝑛 is odd.