Research On The Spectral And Structural Parameters Of Mixed Graphs And Their Related Problems

Spectral graph theory is an important research field on graph theory.It mainly uses algebraic properties of associated matrices to characterize the structural fea-tures of graphs,and studies the intrinsic relations between the spectral parameters of graphs and their structures.In this dissertation,we consider the spectral parameters of mixed graphs,in-cluding H-rank,Hermitian energy,characteristic polynomial,together with struc-ture parameters of mixed graphs and their related problems.Our main results are listed in the following:●In Chapter 2,using the relation between the H-rank and structures of sub-graphs,we firstly determine an upper bound of nullity for n-vertex mixed graphs under the condition of given maximum degree.The corresponding ex-tremal graphs are identified.We secondly consider the relationship between the H-rank rH(DG)of mixed graph DG and the matching number α’(G)(re-sp.independence number α(G)).Then we establish upper and lower bounds on rH(DG)+α(G),rH(DG)-α(G),rH(DG)/α(G),respectively.Finally,with the help of mixed Kronecker,we characterize the upper bound of Hermi-tian energy with respect to H-rank,and show all the corresponding extremal graphs.●In Chapter 3,we first establish the relation between the Hermitian energy and the matching number for mixed graphs,and characterize all extremal mixed graphs by excluding structures of graphs and switching transformations.Furthermore,we obtain sharp bounds on the Hermitian energy of mixed graphs in terms of the vertex cover number.The necessary and sufficient condition for lower bound is given and the upper bound is best possible.Our results extend those main results obtained in[Tian et al.Discrete Appl.Math.222(2017)179-184],[Wang et al.Linear Algebra Appl.517(2017)207-216]and[Wong et al.Linear Algebra Appl.549(2018)276-286].●In Chapter 4,we study the weighted mixed graphs by means of linear mixed graphs and embedded mixed cycles.Based on the structure of graphs,we begin by interpreting all the coefficients of the characteristic polynomial of weighted mixed graphs.Besides,we establish the recurrences for characteris-tic polynomials of weighted mixed graphs.These obtained results naturally contains some results obtained in[Hou et al.Electron.J.Combin.18(1)(2011)156],[Gong et al.Linear Algebra Appl.436(2012)3597-3607]and[Liu et al.Linear Algebra Appl.466(2015)182-207].Let DG be a weighted mixed bipartite cactus graphs.Then we give a necessary and sufficient condi-tion for rH(DG)=2t(t≤α’(G)),and study its minimum H-rank problem as an application.●In Chapter 5,we consider the multiplicity of an Aα-eigenvalue for mixed graph-s and T-gain graphs with a unified approach.To prove an upper bound for the multiplicity of Aα-eigenvalues,we first study the the multiplicity of Aα-eigenvalues for special subgraphs.All the graphs which attain the upper bound are identified.Furthermore,combining with global labeling and algebraic tech-niques,we characterize the multiplicity of a as an Aα-eigenvalue.And a class of graphs sharing the same multiplicities of a as an Aα-eigenvalue is deter-mined.By these results,the corresponding conclusions for undirected graphs,oriented graphs,signed graphs and adjacency spectra,(signless)Laplacian spectra can be deduced.●In Chapter 6,we summarize the main contents of this thesis,and put forward some problems for further research.