Research On The Rank Of Graphs And Related Problems

The rank and the energy of graphs,which both come from the research of chemistry,are two important research topics in spectral graph theory and have always been two hot issues for scholars.In 1957,Collatz and Sinogowitz proposed the following open problem:characterize all graphs satisfying that their rank is smaller than their order.This problem has not been fully solved until now.There are inseparable relations between the rank and the energy of graphs.For a simple(or oriented)graph,its energy(skew energy)is no less than its rank(skew rank).Over the past two years,the Hermitian-adjacency matrix of mixed graphs has been a new research topic of spectral graph theory.What is the relationship between the rank and the energy of Hermitian-adjacency matrix? This problem is also unsolved.In this thesis,we focus on the above two problems and mainly study the skew rank of oriented graphs,the rank of signed graphs,the rank of (?)-gain graphs,the Hermitian Randi(?) matrix and the Hermitian-Randi(?) energy of mixed graphs.The main results are as follows:1.We propose two methods,that is,‘deleting circles method' and ‘deleting edges method',to calculate the skew rank of oriented graphs.Combining the relationship between the skew rank of oriented graphs and that of their subgraphs and ‘deleting circles method',we obtain the skew rank of a class of k cyclic oriented graphs and the corresponding extremal graphs.By using the properties of the skew rank of oriented graphs,the properties of the rank of matrix,‘deleting circles method' and ‘deleting edges method',we characterize all the bicyclic oriented graphs with skew rank 6.We obtain a lower bound of the skew rank of an oriented graph in terms of the rank of its underlying graph and the dimension of cycle spaces by using the rank inequality of matrix,‘deleting circles method'and so on.The corresponding extremal graphs are also characterized.2.We give a method to calculate the rank of signed graphs.Combining this method,the properties of the rank of signed graphs and the rank inequality of matrix,we obtain the relationship between the rank of an unbalanced signed graph and that of its underlying graph in terms of the dimension of cycle spaces.The problem of the relationship between the rank of an arbitrary signed graph and that of its underlying graph is solved.3.We give a method to calculate the rank of (?)-gain graphs.Combining this method,switching function and the properties of the rank of matrix,we characterize all the Tgain bicyclic graphs with rank 2,3 or 4.At the same time,we obtain a lower bound and an upper bound of the rank of a (?)-gain graph ? =(G,?)in terms of the rank of its underlying graph G and the dimension of cycle spaces of G by using ?-transformations and the properties of the rank of matrix.All corresponding extremal graphs are characterized.4.We first define the Hermitian-Randi(?) matrix and Hermitian-Randi(?) energy of mixed graphs.This matrix has the same rank as that of the Hermitian-adjacency matrix.At first,combining with the knowledge of permutation group,we obtain all the coefficients of the characteristic polynomial of Hermitian-Randi(?) matrix.Furthermore,we give some bounds of the Hermitian-Randi(?) energy of mixed graphs in terms of some parameters by using the Cauchy-Schwarz inequality and arithmetic geometric average inequality.All corresponding extremal graphs are also characterized.Finally,we prove that the Hermitian-Randi(?) energy of a mixed tree is the same as the Randi(?) energy of its underlying graph.