Dissertation > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory

Research on Laplace Matrix and Potentially Nilpotent Sign Pattern

Author LiHongHai
Tutor LiJiongSheng
School University of Science and Technology of China
Course Applied Mathematics
Keywords University of Science and Technology of China Eigenvalue Doctoral Dissertation Nilpotent If and only if Standardization Incidence matrix Adjacency matrix Characteristic function Connected graph
CLC O157.5
Type PhD thesis
Year 2007
Downloads 279
Quotes 0
Download Dissertation

Eigenvalues of graphs have been extensively studied since the early developments of graph theory in the 1960s. Most of the early works considered eigenvalues of adjacency matrices of graphs. New developments in the 1980s made it clear that eigenvalues and eigenvectors of the related Laplace matrices of graphs enter the theory in several applications more naturally than those of adjacency matrices. Applications of eigenvalue methods in combinatorics, graph theory and combinatorial optimization have a long history. Laplace matrices of graphs are closely related to the Laplacian, the second order differential operator. This relation yields an important bilateral link between the spectral geometry of Riemannian manifolds and graph theory. The study of sign pattern matrix is a very active research topic in combinatorial matrix theory, whose origin lies in the study of economics, sociology and so on.In this thesis, we study the standard Laplace matrix and the normalized Laplacian of simple graph and signed graph, especially, the properties of their spectra. Furthermore, potentially nilpotent sign pattern matrices in qualitative matrix theory are also characterized. The aim of our study is to extend the results on Laplace matrix to the normalized Laplacian that is a relatively new research field but is important both in theory and application.The paper is organized as follows:In the first chapter, the fundamental notions of graph theory and matrix anlysis are introduced. The developments and main contents of Laplace matrices are presented, then the background, status and applications of researches on Laplace matrices and the normalized Laplacian are introduced. At last, we list all results we obtained in the thesis.In Chapter 2, some notions and the background of signed graphs as well as mixed graphs are firstly introduced. Next we point out the consistency of Laplace matrices between signed graph and mixed graph in essence and list all known results about the location of eigenvalues of Laplace matrices of signed graph and mixed graph. The main purpose of the chapter is to bound the spectral radius of Laplace matrices of signed graph using the Brauer theorem.In Chapter 3, we devote to the properties of the normalized Laplacian of simple graph and signed graph. A series of results on the normalized Laplacian are obtained, such as the connections between the subgraph induced by a vertex subset and a harmonic eigenfunction corresponding to the second least eigenvalue, the components of graph by deleting a cut vertex and the harmonic eigenfunction above. Moreover, it is proved that the second least eigenvalue does not increase by an operation of grafting edges and the condition that the second least eigenvalue strictly decrease is obtained. At last, some basic properties of the normalized Laplacian of signed graph are obtained. In particular, the interlacing eigenvalue properties between signed graph and its underlying graph are investigated. Compared the interlacing result with that of Horn and Johnson, our result is always better than theirs. In this chapter, a new definition about signed graph is firstly introduced, which is used to improve on their result.In the last Chapter, we firstly give a survey on the study status of spectrally arbitrary sign patterns and potentially nilpotent sign patterns and list some obtianed results. The aim of this chapter is to study potentially nilpotent sign patterns. Some double star sign patterns of five order and seven order which are potentially nilpotent are characterized. The necessary conditions for some double star sign patterns being spectrally arbitrary and inertially arbitrary are presented, respectively. In the last section, some potentially nilpotent fork sign patterns with seven order are investigated.

Related Dissertations
More Dissertations