TAILIEUCHUNG - Báo cáo toán học: "The Ramsey number r(K5 − P3, K5)"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The Ramsey number r(K5 − P3, K5). | The Ramsey number r K5 P3 K5 Luis Boza Departamento de Matematica Aplicada I Universidad de Sevilla Seville Spain boza@ Submitted Dec 2 2010 Accepted Apr 4 2011 Published Apr 14 2011 Mathematics Subject Classification 05D10 Abstract For two given graphs G1 and G2 the Ramsey number r G1 G2 is the smallest integer n such that for any graph G of order n either G contains G1 or the complement of G contains G2. Let Km denote a complete graph of order m and Kn P3 a complete graph of order n without two incident edges. In this paper we prove that r K5 P3 K5 25 without help of computer algorithms. 1 Introduction All graphs considered in this paper are simple graphs without loops. For two given graphs G1 and G2 and a given integer n let R G1 G2 n denote the set of all graphs G of order n such that G does not contain G1 and G does not contain G2 where G is the complement of G. The Ramsey number r G1 G2 is the smallest integer n such that R G1 G2 n is empty. The values of r G1 G2 for all graphs G1 and G2 of order at most five up to the three cases that G1 is one of the graphs K5 P3 K5 e and K5 and G2 K5 are found in 1 3 5 6 7 8 9 10 11 12 15 16 17 18 . Kalbfleisch 13 proved that r K5 P3 K5 25 and McKay and Radziszowski 15 found 350904 graphs belonging to R K4 K5 24 c R K5 P3 K5 24 but there might be more of them. Recently Black Leven and Radziszowski 2 proved that r K5 P3 K5 26 and Clavert Schuster and Radziszowski 4 computed the main result of the present paper. This research is supported by the Andalusian Government under project P06-FQM-01649. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P90 1 2 Main result In this paper we find the value of r K5 P3 K5 without help of computer algorithms. The main result is the following Theorem r K5 P3 K5 25. In order to prove Theorem we proceed by reduction to the absurd. Suppose that there exists a graph G G R K5 P3 K5 25 . Since r K4 K5 25 15 we have G contains K4. Let K be the set of cliques of G of order 4 let K G K .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học