Laplacian And Signless Laplacian Matrices Of Graphs

The study of the relations between eigenvalues and structures of graphs is the key problem of spectral graph theory. Given a graph of large order, it is important to capture the information about the graph quickly and correctly. One efficient method is investigating the spectrums of various matrices that can be related to the graph. By examining these eigenvalues it is possible to obtain the information about the graph that might hard to receive. In this dissertation we will focus on the spectrums of two popular matrices related to graphs (Laplacian martix, signless Laplacian martix), since there is a one-to-one relationship between all the (signless) Laplacian coefficients and the (signless) Laplacian spectrum of a graph, we investigate how to use the (signless) Laplacian coefficients to find properties of the graph. This thesis is devoted to discussing the partial ordering of the signless Laplacian coefficients of bicyclic graphs, the partial or-dering of the signless Laplacian coefficients of unicyclic graphs with the matching number and the partial ordering of the Laplacian coef-ficients of unicyclic graphs with the number of leaves. First, we study the signless Laplacian coefficients of bicyclic graphs. Especially, we characterize the minimal elements in the set of all bicyclic graphs of order n with respect to the partial ordering of their signless Laplacian coefficients, moreover, the extremal graphs are not unique. We also present the extremal graphs with minimum incidence energy. Second, we investigate the signless Laplacian coefficients of unicyclic graphs. Especially, we characterize the minimal elements in the set of all uni-cyclic graphs with the matching number with respect to the partial ordering of their signless Laplacian coefficients. The research shows that the extremal graphs are not unique and have different topolog-ical structures from the minimal elements in the set of all unicyclic graphs with the matching number with respect to the partial order-ing of their Laplacian coefficients. Further, the unicyclic graphs with minimum incidence energy are also characterized. At last, we inves-tigate the Laplacian coefficients, which are symmetric polynomials of Laplacian spectrum. We mainly discuss the Laplacian coefficients of unicyclic graphs with the number of leaves, and characterize all min-imal elements with respect to the partial ordering of their Laplacian coefficients and have minimum Laplacian-like energy in some special subsets of unicyclic graphs with the number of leaves and girth.