Spectral properties of digraphs with a fixed dichromatic number
Xiuwen Yang is a PhD student in the department Formal Methods and Tools. Promotors are prof.dr.ir. H.J. Broersma from the faculty of Electrical Engineering, Mathematics and Computer Science, and prof.dr. L. Wang from the Northwestern Polytechnical University, China.
This thesis contains a number of new contributions to the research field that studies the spectral properties of graphs, involving the eigenvalues of different types of matrices associated with these graphs. One of the central problems in this area is the problem of finding the extremal values and characterizing the extremal graphs for invariants involving the eigenvalues of the graph matrix. In this thesis, we restrict ourselves to studying the spectral properties of digraphs, since results on digraphs in this area are relatively scarce.
Commonly studied concepts related to the eigenvalues of digraph matrices are the spectral radius, the k-th spectral moment, the spread, and the sum of k largest eigenvalues. In such studies, one of the approaches is to restrict the attention to digraph classes for which a certain graph parameter is fixed. In this thesis we focus on digraphs with a fixed dichromatic number. With respect to the choice of particular matrices, in this thesis we focus on the spectral properties for the Laplacian matrix, the Aα-matrix, and the eccentricity matrix.
In Chapters 2 and 3, we focus on studying the k-th spectral moment. In Chapters 4 and 5, we focus on studying the spectral radius. In particular, in Chapter 2 we study the k-th spectral moment of the Laplacian matrix of digraphs. In Chapters 3 and 4, we study the k-th spectral moment and spectral radius of the Aα-matrix of digraphs, respectively. In Chapter 5, we study the spectral radius of the eccentricity matrix of digraphs. Our main new contributions to the field can be described as follows.
In Chapter 2, we characterize the digraphs which attain the minimal and maximal Laplacian energy among all digraphs with a fixed dichromatic number. We also determine sharp bounds for the third Laplacian spectral moment among all join digraphs.
In Chapter 3, we obtain the digraphs which attain the minimal and maximal Aα energy among all digraphs with a fixed dichromatic number. We also determine sharp bounds for the third Aα spectral moment among all join digraphs. These results generalize the results about the second and third Laplacian spectral moments of digraphs in Chapter 2.
We find that the Laplacian matrix and the Aα-matrix have much in common with respect to the second and third spectral moments. In particular, the second spectral moments of the Laplacian matrix and the A1/2-matrix are the same. Concerning the spectral radius, scholars often study the spectral radius of the adjacency matrix, signless Laplacian matrix and Aα-matrix. But scholars rarely study the spectral radius of the Laplacian matrix, since the Laplacian matrix is not a nonnegative matrix. Also, the extremal digraphs for the Laplacian spectral radius may be very different from that of the Aα-matrix.
In Chapter 4, we characterize the digraph which has the maximal Aα spectral radius among all digraphs with a fixed dichromatic number, by using the equitable quotient matrix. This provides a new proof of the results by Liu et al. Moreover, we obtain the digraph which has the minimal Aα spectral radius of the join of in-trees with a fixed dichromatic number.
In Chapter 5, we consider bounds for the spectral radius of the eccentricity matrix of join digraphs with a fixed dichromatic number. We attain lower bounds for the eccentricity spectral radius among all join digraphs with a fixed dichromatic number, and give upper bounds for the eccentricity spectral radius of some special join digraphs with a fixed dichromatic number. These extremal digraphs for the eccentricity spectral radius are very different from those in the other chapters.
The eccentricity matrix of a graph is a relatively new matrix. Although there are already several results on eccentricity matrices of graphs, the study regarding eccentricity matrices of digraphs has just begun. The eccentricity matrix seems to be difficult to study. In particular, the eccentricity matrix of a digraph has the additional difficulty of being asymmetric. This is reflected by the complex structure of the extremal digraphs, complicating their characterization.
The asymmetric nature of the matrices associated with digraphs poses a great difficulty for solving problems of the above type. However, since undirected graphs can be considered as a special type of digraphs, results on digraphs are more general, and therefore studying them is worthwhile. Throughout this thesis, we present several open problems that remain unsolved. This shows that there is still much to be explored in this fascinating area of algebraic graph theory.
