{C_2t+1,C≥l}-禁止图的边极值问题研究

Research on Extremal Problems of Edges in {C_2t+1,C≥l}-Free Graphs

摘要: Turán问题是极值图论中的核心研究课题之一。令F表示由一些图组成的集族，如果对任意的F∈F，图G都不包含F作为子图，则称图G是F-禁止图。将Turán数ex(n,F)定义为n个顶点的F-禁止图中的最大边数。令C_2t+1表示长度为2t+1的圈，P_t表示一条长度为l的路，C_≥l表示由长度大于等于l的所有的圈构成的集族。本文主要研究了{C_2t+1,C_≥l}-禁止图以及{C_2t+1,P_t}-禁止图的Turán数，当l>4t-2时，证明了。当l>4t-2为奇数且 时，证明了 。

Abstract: Turán problem is one of the central topics in extremal graph theory. Let F be a family of graphs. If for any F∈F , G does not contain F as a subgraph, then we say G is F-free. The Turán number ex(n,F) is defined as the maximum number of edges in an F-free graph on n vertices. Let C_2t+1 denote a cycle of length 2t+1 , let C_≥l denote a family of cycles with lengths from l to n and let P_t denote a path of length l. In the present paper, we study the Turán number for {C_2t+1,C_≥l} -free graphs and {C_2t+1,P_t} -free graphs. For l>4t-2 , we determine that . For is odd and , we prove that .