Study On The Turán Type Problem Of Matching And Linear Forest

Given two simple graphs T and H.Let Turan number ex(n,H)denote the maximum number of edges of the graph G on n vertices that without H as a subgraph.Generalized Turan number ex(n,T,H)denotes the maximum number of T in an n-vertex graph that without H as a subgraph.When T=K2,the generalized Turan number ex(n,T,H)is the Turan number ex(n,H).A graph is k-degenerate if every subgraph of it contains a vertex of degree at most k.Let N(G,F)represent the number of F subgraphs in the graph G.A linear forest is a graph whose connected components are all paths or isolated.Among them,the linear forest with the largest number of edges is called the largest linear forest of graph G.Let Ks,t*is a graph obtained from Ks,t by substituting the part of size s with a clique of the same size.Recently,the problem about Turan number and the generalized Turan number have received a lot of attention from domestic and foreign scholars.In this paper,we mainly study the problem about the maximal number of cliques and bipartite graphs in degenerate graph,the maximum number of edges in a graph given the number of matches and the minimum number of vertex coverage when n is sufficiently large and the number of cliques and bipartite graphs given the maximum size of linear forest.The specific contents are as follows:In Chapter 2,we study the number of clique and complete bipartite graphs in degenerate graphs.We calculate the exact upper bound of N(G,Kt)in k-degenerate graph G on n vertices,the exact upper bound of N(G,Ks,t)under the condition of s,t?1,n?k+1 and s+t?k and characterize the corresponding extremal graph.In addition,we calculate the maximum number of edges of the graph G on n? 2k+2r2+r+1 vertices when the maximum matching and minimum vertex coverage are determined.In Chapter 3,we study the number of Kr and Ks,t*in linear forests.First,we introduce the shifting method,and further prove that the shifting method can not increase the number of edges of the maximum linear forest.Second,we characterize all the shifted graphs of the largest linear forest with k-1 edges by shifting method.Finally,we calculate the maximum number of Kr and Ks,t*in the graph of the linear forest without k edges on n vertices.