On Extremal Numbers And Saturation Numbers Of Graphs

Graph theory is one of the most important research areas in discrete mathematics,and its concepts and tools play a crucial role in emerging fields such as artificial intelligence and data science.As a core branch of graph theory,extremal graph theory has attracted widespread attention from experts and scholars both domestically and internationally,in both theoretical research and practical applications,making it one of the hottest research directions in the field of mathematics.As is well known,extremal problems form the cornerstone of extremal graph theory.Among them,the most classical problem is the determination of extremal numbers.Specifically,the study concerns determining the extremal number ex(n,H)for a given graph H,which represents the maximum number of edges in a graph with n vertices that does not contain any copy of H.The earliest results on such problems can be traced back to Mantel’s theorem in 1907,which determined the extremal number when H=K3,denoted by ex(n,K3).In 1941,Turán extended Mantel’s theorem to the general complete graph H=Kt,determining ex(n,Kt).This result,known as Turán’s theorem,is widely considered the starting point of extremal graph theory and has inspired subsequent research on extremal problems.Corresponding to the extremal number problem,the saturation number problem is also a long-standing topic.It mainly investigates H-saturated graphs,which are graphs not containing any copy of H but adding any new edge results in a copy of H.The minimum number of edges inH-saturated graphs with n vertices is known as the saturation number,denoted by sat(n,H).In 1964,inspired by the Erd(?)s-Gallai conjecture,Erd(?)s,Hajnal and Moon introduced the concept of saturation number and determined sat(n,Kt).Subsequently,scholars conducted extensive research on saturation problems.According to the definitions of extremal numbers and saturation numbers,it is known that any H-saturated graph G with n vertices satisfies sat(n,H)≤e(G)≤ex(n,H).This naturally raises the question:for any integer m satisfying sat(n,H)≤m≤ex(n,H),does there exist an H-saturated graph with n vertices and exactly m edges?To investigate this problem,the concept of saturation edge spectrum is introduced.The saturation edge spectrum of H,denoted by ES(n,H),refers to the set of all edge numbers in Hsaturated graphs with n vertices.The main focus of this paper is to study extremal numbers,saturation numbers and saturation edge spectra of certain graphs.This thesis has five chapters,which is organized as follows.In Chapter 1,we introduce some basic notations and terminology in extremal graph theory,briefly introduce some major developments in extremal numbers,saturation numbers and saturation edge spectra.Then we present our main results in this thesis.Chapter 2 delves into the extremal numbers of certain classes of disjoint cliques.We begin by investigating the extremal numbers of disjoint cliques tKp+1,inspired by Simonovits’ study of ex(n,tKp+1).Specifically,we determine ex(n,3Kp+1)and ex(t(p+1),tKp+1)for all integers n,t and p≥2,generalizing Simonovits’ results.Additionally,by characterizing all extremal graphs Ex(t(p+1),tKp+1),we prove that extremal graphs of tKp+1 are not unique for small values of n and t>2p.Furthermore,we explore the extremal numbers of disjoint cliques in complete multipartite graphs,determining ex(Kn1,n2,...,nr,kK3 under the conditions r≥ 4 and 10k-4≤n1+4k≤n2≤n3≤…≤nr.This result also partially confirms the conjecture by Han and Zhao regarding ex(Kn1,n2...,nr,kKt).In Chapter 3,we investigate the saturation numbers of several classes of graphs.For t≥ 2,k≥ 3 and sufficiently large n,Chen,Faudree,Faudree,Gould,Jacobson and Magnant provided upper bounds and lower bounds for the saturation number sat(n,tPk)and proposed conjectures regarding sat(n,tPk).In this chapter,we first improve the general lower bound for sat(n,tP3)and determine the value of sat(n,tP3)for t=4 and n≥3t+2,and for t=5 and n≥ 3t+1.Furthermore,we construct counterexamples for k∈{4,5}.Additionally,concerning the conjecture by Pikhurko and Schmitt that sat(n,K3,3)=(3+o(1))n,for any n≥9,we provide an upper bound for sat(n,K3,3)of 3n-9,and we also establish that 3n-9 serves as a lower bound for the number of edges when the minimum degree of a K3,3-saturated graph is at most 2 or at least 5.Chapter 4 explores the saturation edge spectra of graphs.As of today,the saturation edge spectra of the following graph classes have been determined,including complete graphs,the diamond graph,stars,paths with at most six vertices,and the cycle with five vertices.Furthermore,we investigate the saturation edge spectra of cycle subdivisions and determine ES(n,C≥k)for any k∈｛3,4,5,6}.Specifically,for any k∈{3,4,5},we prove that ES(n,C≥k)=[sat(n,C≥k),ex(n,C≥k)].Additionally,if n≡2(mod 4)or n≡ 3(mod 4),then ES(n,C≥6)=[sat(n,C≥6),ex(n,C≥6)],and if n≡0(mod 4)or n≡1(mod 4),then ES(n,C≥6)≠[sat(n,C≥6),ex(n,C≥6)].In Chapter 5,we summarize the results in this thesis and put forward some problems for further research.