The Ordering Of The Connected Graphs With The Smallest Laplacian Spectral Radii

There are various matrices that are naturally associated with a graph, suchas the adjacency matrix, the incidence matrix, the distance matrix and the Lapla-cian matrix. One of the main problems of algebraic graph theory is to determineprecisely how, or whether, properties of graphs are reflected in the algebraic prop-erties (especially eigenvalues) of such matrices.Among the above mentioned matrices of graphs, the most important are theadjacency matrix and the Laplacian matrix of graphs. Both the eigenvalues ofthe Laplacian matrix and the adjacency matrix are the invariants of graphs underisomorphism. The latter was much more investigated in the past several decadesand has formed a rather mature theory now (see [3, 14, 21]). However, since theeigenvalues of the Laplacian matrix have more natural relation to the structureof graph and can reflect more properties of graphs, they are payed more attentionto and have become a hot research direction now.Among all the eigenvalues of Laplacian matrix, the most important is thelargest Laplace eigenvalue, which is called the Laplacian spectral radius of a graph.In recent years, domestic and foreign scholars have made particular progress onthe research of it. Some have given several good upper boundaries of Laplacianspectral radius (see [23, 24, 73, 75, 76, 79, 90, 93, 105]). Besides, some haveconsidered the variation of Laplacian spectral radius of some special graphs underoperations of grafting, subdivision and contracting (see [47]).Our paper is mainly about the ordering of the connected graphs with thesmallest Laplacian spectral radii.In the first chapter, we have introduced the research background and someresearch achievements of Laplacian spectral radius, and we also introduce somebasic conceptions on algebraic graph.It is well known that tree is the simplest connected graph. Then our researchbegins from tree. In the second chapter, we primarily consider the ordering of thetrees of order n with the smallest Laplacian spectral radii. In [1], Xi-ying Yuanet al use the operations of grafting, subdivision and contracting on the trees toobtain the ordering of the first seven trees of order n with the smallest Laplacianspectral radii. In this chapter, we continue this ordering and extend this orderingto the 11th tree.We can obtain a unicyclic graph by arbitrarily adding a new edge to a tree andcan obtain a bicyclic graph by arbitrarily adding a new edge to a unicyclic graph.So, in the following third chapter, we primarily consider the Laplacian spectralradius of unicyclic graphs and bicyclic graphs of order n and have found the secondto the fifth unicyclic graphs of order n with the smallest Laplacian spectral radiiand the bicyclic graph of order n with the smallest Laplacian spectral radii.In the last fourth chapter, by using the results in chapter two and three, we have given the first fourteen connected graphs with the smallest Laplacian spectralradii among all the connected graphs of order n, which reach the nine smallestvalues of the Laplacian spectral radii among all connected graphs of order n whenn is even (where some graphs are juxtaposed) and reach the eight smallest valuesof the Laplacian spectral radii when n is odd (where some graphs are juxtaposed).