Relations Between Matching Number And Several Algebraic Parameters Of Graphs

Spectral Graph Theory is an important research branch of Algebraic Graph Theory and Combinatorial Matrix Theory,the core of which is combining graphs with matri-ces,aiming to reveal the structure properties of those graphs by studying the spectra(or eigenvalues)of the corresponding matrices.There are three important research di-rections in Spectral Graph Theory:characterizing the lower and upper bounds of the spectral radius within some class of graphs and determining the corresponding extremal graphs,the problem of nullity and rank of graphs and the problem about graph ener-gy,which attract much attention from experts in Graph Theory since they have many applications in Quantum Chemistry,Theoretical Chemistry,Communication Network and Informatics.This thesis mainly deals with the function of matching number in above three directions of Spectral Graph Theory,in which the relations between matching number and spectral radius,nullity of graphs,rank of graphs and graph energies are established,respectively.It is partitioned into five chapters.Chapter 1 introduces the background,the current research status,the main results,and some notations used in this thesis.Chapter 2 investigates the relation between matching number and distance Lapla-cian spectral radius.Let G be an undirected simple graph with order n.The lower bound of the distance Laplacian spectral radius ?L(G)in terms of matching number m(G)is obtained:pL(G)? n if m(G)=[n/2],and equality holds if and only if G = Kn;?L(G)? 2n-m(G)if 1 ? m<[n/2]-1,and equality holds if and only if G is a spanning subgraph of Km(?)Kn-m and G contains Km,n-m as a spanning subgraph.Chapter 3 studies the relation between matching number and the nullity(rank)of mixed graphs.First,using the matching number m(G)and the order of a mixed unicyclic graph G,we formulate the nullity ?H(G)of the Hermitian adjacency matrix of G.Moreover,the mixed graphs with rank 3 for the Hermitian adjacency matrix are characterized,which are determined by their Hermitian adjacency spectra under switching equivalence.At last,let G be a mixed graph with matching number m(G)and cycle space dimension ?(G).The lower and upper bounds of the rank ?H(G)for the Hermitian adjacency matrix of G are presented:2m(G)-2?(G)??H(G)?2m(G)+ ?(G).In addition,the extremal graphs attaining the lower and upper bounds are characterized completely.Chapter 4 focuses on the relation between matching number and graph energy.Let G? be an oriented graph with G as the underlying graph.The lower bound of the skew-energy ?S(G?)of the skew-adjacency matrix of G? in terms of the matching number m(G)is presented as ?S(G?)? 2m(G),and equality holds if and only if G?is switching-equivalent to(?),where ?' assigns all edges the same direction from one partition to the other.Additionally,for an undirected simple triangle-free graph G,the upper bound of the energy ?(G)in terms of the matching number m(G)and the maximum edge-degree ?e is derived:?(G)? 2m(G)(?)if ?e is even,and equality holds if and only if G is the disjoint union of ?(G)copies of path P2 and some isolated vertices;?(G)?m(G)((?))(a = 2(?e+1))if ?e is odd,and equality holds if and only if G is the disjoint union of ?(G)copies of path P3 and some isolated vertices.The last chapter,Chapter 5,summarizes the main conclusions of this thesis andpresents some problems for further investigation.