Research On The Spectral And Structure Parameters Of Graphs And Their Related Problems

Graph spectral theory is an important research field on algebraic graph theory and combinatorial matrix theory.It mainly uses the spectral parameters described by the matrices associated to graphs to characterize the structural properties of the graphs,and studies the intrinsic relations between the spectral parameters of graphs and their structures.In this thesis,using graph transformations,function construc-tion and derivation and mathematical induction,we study the spectral parameter-s,including adjacent spectra,distance spectra,normalized Laplacian spectra,and structure parameters of graphs and their related problems.Our main results are listed in the following:·In Chapter 2,we completely determine the normalized Laplacian spectrum on Tk(G)(resp.Qk(G))in terms of that of G for any connected graph G,k≥2.As applications,the correlation between the degree-Kirchhoff index,the Kemeny’s constant and the number of spanning trees of the r-th iterative k-triangle graph Ttk(G))(resp.the γ-th iterative k-quadriLateral graph Qγk(G))and those of G are derived.Our results extend those main results obtained in[Xie et al.,Appl.Math.Comput.273(2016)1123-1129]and[Li et al.,Appl.Math.Comput.297(2017)180-188].·In Chapt,er 3,first we give a necessary and sufficient condition for the integrali-ty of Cayley graphs over generalized dihedral groups,which naturally contains the main results obtained in[J.Algebraic Combin.47(2018)585-601].Sec-ond a closed-form decomposition formula for the distance matrix of Cayley graphs over any finite groups is derived.As applications,a nece.ssary and suf-ficient,condition for the distance integrality of Cayley graphs over generalized dihedral groups is displayed.Some simple sufficient(or necessary)conditions for the integrality and distance integrality of Cayley graph are exhibited,re-spectively,from which several infinite families of integral and distance integral Cayley graphs are constructed.Finally,some necessary and sufficient condi-tions for the equivalence of integrity and distance integrity of Cayley graphs over generalized dihedral groups are obtained.·In Chapt,er 4,we consider the correlation involving the skew-rank,the inde-pendence number,and some other parameters.First a sharp lower bound on sr(Gσ)+ 2α(G)is determined.Then sharp lower bounds on sr(Gσ)+α(G),sr(Gσ)a(G)and sr(Gσ)/a(G)are obtained.All the corresponding extremal oriented graphs Gσ are characterized,respectively.·In Chapter 5,first we provide the comple.te information for the eigenvalues of the probability transition matrix of a random walk on Q(G)in terms of those of G.Then the expected hitting time between any two vertices of Q(G)in terms of those of G is completely determined.Finally,as applications,the corre.lation be.tween the degree-Kirchhoff index(resp.Kemeny’s constant,number of spanning trees)of Q(G)and G is derived.Furthermore,based on the relationship of the expected hitting time between any two vertices of Q(G)and G,the resistance distance between any two vertices of Q(G)is presented in terms of that of G.· In Chapter 6,we display a close relation between hitting times of the simple random walk on a graph,the.Kirchhoff index,the resistance-centrality,and related invariants of unicyclic graphs.In addition,we determine the sharp upper and lower bounds on the cover cost(resp.reverse cover cost)of a vertex in an n-vertex unicyclic graph.All the corresponding extremal graphs are.identified.·In Chapter 7,we summarize the main contents of this paper and put forward some problems for further research.