The Second Largest Eigenvalue And Spectral Radius Of A Mixed Graph

The Laplacian matrix of a simple graph receives attentions in 70's of the 20th century, and gradually becomes the research topic of algebraic graph theory, which has many beautiful results, especially on the relations between the eigenvalues of the Laplacian matrix and numerous graph invariants. In recent yesrs, attention has been turned to the study of the Laplacian matrix of a mixed graph or a signed graph.In this paper, two topics on Laplacian eigenvalues of the mixed graphs have been studied, which are respectively the relation between the eigenvalues and the degrees of vertices, and the characterization of mixed graph whose spectral radius attains the maximum over all mixed graphs with given order.Let G be a simple connected graph on n vertices which has at least three vetice and one edge. Let d₁(G),d₂(G) be the first largest and the second largest degree respectively, and letλ₁(G),λ₂(G) be the first largest and the second largest eigenvalues of the Laplaeian matrix of G respectively. Grone and Merris showed that (â…°)λ₁(G)≥d₁(G)+1; and Li and Pan proved that (â…±)λ₂(G)≥d₂(G). Zhang and Luo proved the result (â…°) also holds for mixed graphs. Wether the result (â…±) holds for mixed graph? We focus on this problem and give a sufficient condition for (â…±).Fan characterized respectively the unicyclic mixed graphs of given order whose Laplacian spectral radii attain the maximum and the minimum, and further determined respectively the unicyelic mixed graphs of given order whose Laplacian spectral radii attain the second and the third largest maximum. Fan, Tam and the author of this thesis characterized the unique bicyclic mixed graph of given order whose Laplacian spectral radius attains the maximum. It is natural to consider the same problem for mixed graphs of given order and with fixed nullity. In this thesis, we use a unified method to deal with above problem on mixed graphs with nullity less than 4.This paper contains three chapters. In the first chapter, we give some preliminary knowledge which is necessary in the paper. In chapter 2, we discuss the relation betweenλ₂(G) and d₂(G), and obtain a sufficient condition forλ₂(G)≥d₂(G). A mixed graph is called maximizing if its Laplacian spectral radius attains the maximum among all mixed graphs with the same number of vertices and edges. In chapter 3, we characterize maximizing graphs with nullity less than 4 by a unified method.