Graphs with maximal signless Laplacian spectral radius
Graphs with maximal signless Laplacian spectral radius
复制标题
DOI：
10.1016/j.laa.2009.11.027
复制
发表时间：
2010-03
影响因子：
1.1
通讯作者：
Ting Chang;B. Tam
中科院分区：
文献类型：
--
作者：
Ting Chang;B. Tam
对于（简单）图 G 的无符号拉普拉斯，我们指的是矩阵 Q(G)=D(G)+A(G)，其中 A(G)、D(G) 分别表示 G 的邻接矩阵和顶点度数的对角矩阵。已知，在具有给定数量的顶点和边的所有连通图上，使无符号拉普拉斯谱半径 ρ(Q(G)) 最大化的连通图 G 是（度）最大的。对于具有 n 个顶点和 r 个不同顶点度 δr>δr-1>⋯>δ1 的最大图 G，证明对于具有 n+1（分别为 n）个顶点且边数与 G 相同的某个最大图 H，ρ(Q(G))<ρ(Q(H))，如果 G 正好有两个支配顶点或分别存在整数 i,2⩽i⩽r2，如果存在正整数si,l和l+2⩽i⩽r2，使得δi+δr+1-i⩽n+1（分别为δi+δr+1-i⩽δl+δr-l+1）。在具有 m 个边和 m-k 个顶点（k=0,1,2,3）的图类上最大化 ρ(Q(G)) 的图已完全确定。
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), 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>⋯>δ1, it is proved that ρ(Q(G))<ρ(Q(H)) 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⩽r2respectively, if there exist positive integersi,lwithl+2⩽i⩽r2 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 m-k vertices, for k=0,1,2,3, are completely determined.