TAILIEUCHUNG - Báo cáo toán học: "The independence number of graphs with large odd girth"

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í toán học quốc tế đề tài: The independence number of graphs with large odd girth. | The independence number of graphs with large odd girth Tristan DENLEy Department of Pure Mathematics and Mathematical Statistics University of Cambridge 16 Mill Lane Cambridge CB2 1SB England. Submitted August 6 1994 Accepted September 17 1994. Abstract. Let G be an F-regular graph of order n and independence number ữ G . We show that if G has odd girth 2k 3 then G n 1 kF1 k. We also prove similar results for graphs which are not regular. Using these results we improve on the lower bound of Monien and Speckenmeyer for the independence number of a graph of order n and odd girth 2k 3. AMS Subject Classification. 05C15 1. Introduction Let G be a triangle-free graph of order n with average degree d and independence number G . There has been great interest in finding good lower bounds for a G in terms of d and producing polynomial-time algorithms which find large independent sets of G. In 1 and 2 Ajtai Komlós and Szemeredi made a breakthrough in this area when they provided a polynomial algorithm to find an independent set of size at least n log d G . v 7 - 100d Correspondence to Tristan Denley Matematiska institutionen Umeả universitet Umea Sweden Email to tristan@ 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 1 1994 R9 2 A little later this algorithm was sharpened by Griggs in 5 improving the constant from 100-1 to . Shearer in 8 improved this bound still further to give that Gl g d - d 1 G 4 d-1 2 J. In 8 besides extending this result to take the degree sequence of the graph into account Shearer also considered what could be said for graphs of larger odd girth. He proved the following theorem. Theorem A. Let G be a graph of order n with degree sequence d1 d2 . dn. Suppose that G contains no 3 or 5 cycles. Let n11 be the number of pairs of adjacent vertices of degree 1 in G. Let f 0 1 f 1 4 7 and f d 1 d2 d f d 1 d2 1 -1 When d 2. Then G Xx f di n11 7 . i 1 The results of this paper are designed to deal with the case when the average degree of the .

• Báo cáo khoa học
• 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
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội