TAILIEUCHUNG - Báo cáo toán học: " Independence number and disjoint theta graphs"

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: Independence number and disjoint theta graphs. | Independence number and disjoint theta graphs Shinya Fujita Colton Magnant Submitted Aug 16 2009 Accepted Jul 10 2011 Published Jul 22 2011 Mathematics Subject Classification 05C35 Abstract The goal of this paper is to find vertex disjoint even cycles in graphs. For this purpose define a ớ-graph to be a pair of vertices u v with three internally disjoint paths joining u to v. Given an independence number a and a fixed integer k the results contained in this paper provide sharp bounds on the order f k a of a graph with independence number a G a which contains no k disjoint ớ-graphs. Since every ớ-graph contains an even cycle these results provide k disjoint even cycles in graphs of order at least f k a 1. We also discuss the relationship between this problem and a generalized ramsey problem involving sets of graphs. 1 Introduction The search for vertex disjoint subgraphs of a graph has been considered in many contexts. The most popular such subgraph has certainly been the cycle. Many different conditions have been established for the existence of vertex disjoint cycles see 1 6 12 19 24 . From there people went on to impose restrictions on the cycles. In particular some people imposed length restrictions see 3 14 16 others forced cycles to contain particular vertices or edges see 7 13 while still others forced the cycles to be chorded see 4 10 17 . See 18 for a survey of degree conditions for disjoint cycles. The structure of this paper follows that of Egawa Enomoto Jendrol Ota and Schier-meyer 12 . There the authors present many results concerning disjoint cycles in graphs with given independence number. Specifically they define a function g k a to be the maximum integer n such that there exists a graph G on n vertices with independence number a G a and G contains no k disjoint cycles. Similarly let g k a be the maximum integer n such that there exists a graph G on n vertices with independence number a G a and G contains no k disjoint even cycles. As Gunma National

• 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