tailieunhanh - Báo cáo toán học: "Two Extremal Problems in Graph Theory"

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: Two Extremal Problems in Graph Theory. | Two Extremal Problems in Graph Theory Richard A. Brualdi and Stephen Meilendorf Department of Mathematics University of Wisconsin Madison WI 53706 July 21 1998 Abstract We consider the following two problems. 1 Let t and n be positive integers with n t 2. Determine the maximum number of edges of a graph of order n that contains neither Kt nor Kt t as a subgraph. 2 Let r t and n be positive integers with n rt and t 2. Determine the maximum number of edges of a graph of order n that does not contain r disjoint copies of Kt. Problem 1 for n 2t is solved by Turan s theorem and we solve it for n 2t. We also solve Problem 2 for n rt. 1 Introduction One of the best known results in extremal graph theory is the following theorem of Turán. Theorem 1 Let t and n be positive integers with n t 2. Then the maximum number of edges of a graph of order n that does not contain a complete subgraph Kt of order t equals n - E n 1 2 2 v 7 i 1 where n n1 nt_1 is a partition of n into t 1 parts which are as equal as possible. Furthermore the only graph of order n whose number of edges equals 1 that does not contain a complete subgraph Kt is the complete t 1 -partite graph Kni nt_1 with parts of sizes n-1 . nt_1 respectively. In general the extremal graph Kni nt_1 in Theorem 1 contains a complete bipartite subgraph Kt t. This suggests the following problem. Research partially supported by NSF Grant DMS-9123318. 1 Research partially supported by a Department of Education Fellowship administered by the University of Wisconsin-Madison. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 1 1994 R2 2 Problem 1 Let t and n be positive integers with n t 2. Determine the maximum number of edges of a graph of order n that contains neither Kt nor Kt t as a subgraph. If n 2t then Problem 1 is equivalent to Turan s theorem. The case n 2t is settled in the next theorem. If G and H are graphs then their sum is the graph G H obtained by taking disjoint copies of G and H and putting an edge between each vertex of