Graphs with maximal signless Laplacian spectral radius

✍ Scribed by Ting-Jung Chang; Bit-Shun Tam

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 340 KB
• Volume: 432
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2009.11.027

✦ Synopsis

By the signless Laplacian of a (simple) graph G we mean the matrix

, where A(G), D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. It is known that connected graphs G that maximize the signless Laplacian spectral radius ρ(Q (G)) over all connected graphs with given numbers of vertices and edges are (degree) maximal. For a maximal graph G with n vertices and r distinct vertex degrees δ r > δ r-1 >

for some maximal graph H with n + 1 (respectively, n) vertices and the same number of edges as G if either G has precisely two dominating vertices or there exists an integer i, 2 i r 2 respectively, if there exist positive integers i, l with l + 2 i r 2 such that δ i + δ r+1-i n + 1 (respectively, δ i + δ r+1-i δ l + δ r-l + 1). Graphs that maximize ρ(Q (G)) over the class of graphs with m edges and mk vertices, for k = 0, 1, 2, 3, are completely determined.