Research On The Diameter And Skew Rank Of Graphs

In order to investigate the structural property of graphs, many kinds of ma-trices are introduced, such as the adjacency matrix, the Laplacian matrix and the signless Laplacian matrix, which are all real symmetric matrices. Recently the skew-adjacency matrix of an oriented graph have received many attentions, which is a skew symmetric matrix. Assigning a direction for each edge of a simple graph G, we will get an oriented graph Gσ’. The skew-adjacency matrix of Gσ was defined according to the directions of edges.According to the viewpoint of Cavers et. al, the spectra of the skew-adjacency matrices of a graph are considered as a possible way to distinguish adjacency cospec-tral graphs. They also introduced some topics in the research of the spectra of oriented graphs. Establishing the relationship between the structural property and the spectral property is a fundamental problem in spectral graph theory. Some invariants such as skew rank, skew energy and skew spectral radius have received extensive attention.The skew rank of a oriented graph is defined as the rank of its skew-adjacent matrix. In 2009 B. Shader firstly investigated the skew rank of oriented graphs. In 2015 Li and Yu characterized the oriented graphs with skew rank 2 and some special graphs with skew rank 4. In this paper we find that the diameter of an oriented graph is at most the skew rank. So, it is very important to characterize the graph with the same diameter and skew rank. We characterize the graphs with with diameter and skew rank both equal to 4.The organization of the thesis is as follows. In Chapter one we briefly introduce the background and development of the spectra and skew rank of graphs, some basic concepts and notations, and the problem and results in the thesis. In Chapter two we prepare some lemmas and conclusions which will be used later. We give a basic result, that is, the diameter of an oriented graph is at most the skew rank. We also discuss the property of a path with length equal to diameter called diameter path. In Chapter three, we obtain the main result, i.e. the characterization of oriented graphs with diameter and skew rank both equal to 4. We prove that the vertices outside a diameter path have at most three neighbors in the path. We discuss the distribution of three kinds of vertices, and then arrive at the main result of this thesis.