Edge perturbation on graphs with clusters: Adjacency, Laplacian and signless Laplacian eigenvalues

详细信息    查看全文

• 作者：Domingos M. Cardoso^a ; ^{dcardoso@ua.pt" class="auth_mail" title="E-mail the corresponding author} ; Oscar Rojo^b
• 关键词：05E30 ; 15A18 ; 05C50
• 刊名：Linear Algebra and its Applications
• 出版年：2017
• 出版时间：1 January 2017
• 年：2017
• 卷：512
• 期：Complete
• 页码：113-128
• 全文大小：371 K

文摘

Let G be a simple undirected graph of order n. A cluster in G of order c and degree s  , is a pair of vertex subsets (C,S)$(C,S)$, where C   is a set of cardinality |C|=c≥2$|C|=c\ge 2$ of pairwise co-neighbor vertices sharing the same set S of s neighbors. Assuming that the graph G   has k≥1$k\ge 1$ clusters (C₁,S₁),…,(C_k,S_k)$(C_1,S_1),\dots ,(C_k,S_k)$, consider a family of k   graphs e5092a8df7cb" title="Click to view the MathML source">H₁,…,H_k$H_1,\dots ,H_k$ and the graph G(H₁,…,H_k)$G(H_1,\dots ,H_k)$ which is obtained from G   after adding the edges of the graphs e5092a8df7cb" title="Click to view the MathML source">H₁,…,H_k$H_1,\dots ,H_k$ whose vertex set of each H_j$H_j$ is identified with C_j$C_j$, for j=1,…,k$j=1,\dots ,k$. The Laplacian eigenvalues of G(H₁,…,H_k)$G(H_1,\dots ,H_k)$ remain the same, independently of the graphs e5092a8df7cb" title="Click to view the MathML source">H₁,…,H_k$H_1,\dots ,H_k$, with the exception of |C₁|+⋯+|C_k|−k$|C_1|+\cdots +|C_k|-k$ of them. These new Laplacian eigenvalues are determined using a unified approach which can also be applied to the determination of a same number of adjacency and signless Laplacian eigenvalues when the graphs e5092a8df7cb" title="Click to view the MathML source">H₁,…,H_k$H_1,\dots ,H_k$ are regular. The Faria's lower bound on the multiplicity of the Laplacian eigenvalue 1 of a graph with pendant vertices is generalized. Furthermore, the algebraic connectivity and the Laplacian index of G(H₁,…,H_k)$G(H_1,\dots ,H_k)$ remain the same, independently of the graphs e5092a8df7cb" title="Click to view the MathML source">H₁,…,H_k$H_1,\dots ,H_k$.