Ordering (signless) Laplacian spectral radii with maximum degrees of graphs

摘要

Let lambda(G) and mu(G) be the Laplacian and signless Laplacian spectral radius of a graph G, respectively, and let Delta(G) be the maximum degree of G. We call a graph G an (n, m) graph if G contains n vertices and m edges. In this paper, we prove that for two connected (n, m) graphs G and G', if Delta(G) >= m - n-3/2 and Delta(G) > Delta(G'), then lambda(G) > lambda(G') and mu(G) > mu(G'), and the bound "m - n-3/2" is optimal for the case of signless Laplacian spectral radius. Moreover, we use an example to illustrate that, as a consequence of our new result, when m <= [3n-5/2], the ordering of connected (n, m) graphs according to their largest (signless) Laplacian spectral radii can be transfer to the ordering of connected (n, m) graphs with large maximum degree and hence we can conclude that it is not a difficult problem to ordering connected (n, m) graphs via their largest (signless) Laplacian spectral radii.

关键词