Research On The Rank Of Mixed Graphs

Spectral graph theory is an important branch of algebraic graph theory.Scholars study the relationship between spectral parameters and structural parameters of graphs,and they use the spectral properties of graphs to describes the structural properties of graphs.Spectral graph theory originated in the field of quantum chemis,try and it ia used in many fields of science.Mixed graph is obtained by orienting partial edges of an undirected graph.Simple graph and oriented graph are two extremely cases of mixed graph.In 2015,Mohar et al.and Xueliang Li et al.proposed the concept of Hermite adjacency matrix of mixed graphs independently.Since then,the Hermite spectrum of mixed graphs has become a hot research topic in spectral graph theory.As an important spectral parameter of graphs,rank has been attained much attention.This thesis mainly discusses the relationship between the rank of graph and the structural parameters in the process of orientation.When all edges of the graph are oriented,we consider the skew-rank sr(G?)of the oriented graph G? and the rank r(G)of the underlying graph.We consider the continuity of the difference between these two parameters.We proved that there is no oriented graph G? with sr(G?)-r(G)=2c(G)-1.Furthermore,we construct infinite connected oriented graphs G? which satisfy c(G)=k and sr(G?)-r(G)=2c(G)-k,where 0 ?l ?4k and l?1.When the graph is partially oriented,we consider the relationship between the H-rank rk(G)of the mixed graph G and the matching number m(G),the cycle space dimension c(G).We consider the continuity of the H-rank.We proved that there is no mixed graph with rk(G)=2m(G)-2c(G)+1.And then we construct infinite connected mixed graphs G which satisfy c(G)=k and rk(G)=2m(G)-2c(G)+l,where 0?l?3k and l?1.The structure of this paper is as follows:In the first chapter,we introduces the relevant research background,then we introduce the basic concepts involved in this paper and the necessary related notations,and finally we introduce the research problems,their developments and the main results obtained in this thesis.In the next chapter,we discuss the relationship between the skew-rank of oriented graph and the rank of its underlying graph.We prove that there is no oriented graph satisfied sr(G?)-r(G)=2c(G)-1.In chapter 3,we discuss the relation between H-rank of the mixed graphs and matching number and cyclomatic number.We prove that there is no mixed graph satisfied rk(G)=2m(G)-2c(G)+1.