Ramsey Numbers for Theta Graphs. (15th June 2011)

• Record Type: Journal Article
• Authors: Jaradat, M. M. M.; Bataineh, M. S. A.; Radaideh, S. M. E.
• Other Names: Panholzer Alois Academic Editor.
• Is Part Of: International journal of combinatorics. Volume 2011(2011)
• Publication Date: 2011-06-15
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Periodicals; Electronic journals; 511.605
• DOI: 10.1155/2011/649687
• Languages: English
• ISSNs: 1687-9163

Abstract

Abstract : The graph Ramsey numberR ( F 1, F 2 ) is the smallest integerN with the property that any complete graph of at leastN vertices whose edges are colored with two colors (say, red and blue) contains either a subgraph isomorphic toF 1 all of whose edges are red or a subgraph isomorphic toF 2 all of whose edges are blue. In this paper, we consider the Ramsey numbers for theta graphs. We determineR ( θ 4, θ k ), R ( θ 5, θ k ) fork ≥ 4 . More specifically, we establish thatR ( θ 4, θ k ) = R ( θ 5, θ k ) = 2 k - 1 fork ≥ 7 . Furthermore, we determineR ( θ n, θ n ) forn ≥ 5 . In fact, we establish thatR ( θ n, θ n ) = ( 3 n / 2 ) - 1 ifn is even, 2 n - 1 ifn is odd.