Research On Several Problems In Spectral Extremal Graph Theory

Extremal graph theory mainly studies the problem of maximizing or minimizing some variables of graphs in a given graph class,including edge number,minimum degree,diameter,connectivity,etc,and characterizing the extremal graphs The most typical problem in extremal graph theory is Turán type extremal problem,which is to find the maximum number of edges of a graph that does not contain a given graph H as a subgraph and characterize the extremal graphs.Spectral extremal graph theory mainly studies the spectral properties of various matrices associated with graphs,including adjacency matrix,Laplace matrix,or signless Laplace matrix,etc.,especially the spectral radius or other eigenvalues and eigen-vectors of graphs without special substructures.In this dissertation we focus on Erd?s-Gallai stability theorem for linear forests,adjacent and signless Laplacian spectral extremal results of graphs with forbidding linear forests.Moreover,we also study the signless Laplacian spectral radius of graphs with forbidding Ks,t-minor.and give spectral conditions for a graph to be Hamilton-connected·In chapter 2,we obtain a stability version of the Erd?s-Gallai theorem in terms of minimum degree.Let G be a connected graph of order n and F=(Ui=1kP2ai)?(?i=1lO2bi+1)be k+l disjoint paths of order 2a1m...,2ak,2b1+1,...,2bl+1,respectively,where k?0,0?l?2,and k+l? 2.If the minimum degree ?(G)??i=ik ai+?i=1l bi-1,then F(?)G except several classes of graphs for sufficiently large n,which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.·In chapter 3,we determine the maximum spectral radius of all graphs without a linear forest as a subgraph and all the extremal graphs.In addition,the maximum number of edges and spectral radius of all bipartite graphs without kP3 as a subgraph are obtained and all the extremal graphs are also determined Moreover,some relations between Turán type extremal problems and their spectral counterparts are discussed.·In chapter 4,we investigate all graphs of sufficiently large order n which do not contain linear forests as a subgraph.We first give a stability theorem for kP3 in terms of the number of edges and then this stability theorem is used to determine the unique graphs maximizing the signless Laplacian spectral radius over graphs which do not contain kP3 as a subgraph.Moreover,we determine unique graphs maximizing the signless Laplacian spectral radius over graphs which do not contain linear forests F with at most two odd paths and F?kP3 as a subgraph.·In chapter 5,we prove that if G is a K2,t-minor free graph of order n ? t2+4t+1 with t? 3,the signless Laplacian spectral radius q(G)?1/2(n+2t-2+(?)with equality if and only if n?1(mod t)and G=F2,t(n).In particular,if t=3 and n?22,then F2,3(n)is the unique K2,3-minor free graph of order n with the maximum signless Laplacian spectral radius.In addition,F3,3(n)is the unique extremal graph with the maximum signless Laplacian spectral radius among all K3,3-minor free graphs of order n>1186.·In chapter 6,we prove that a simple graph G of order sufficiently large n with the minimum degree ?(G)? k? 2 is Hamilton-connected except for two classes of graphs if the number of edges in G is at least 1/2(n2-(2k-1)n+2k-2).In addition,this result is used to present sufficient spectral conditions for a graph with large minimum degree to be Hamilton-connected in terms of spectral radius or signless Laplacian spectral radius,which extends the results of Zhou and Wang[96].