Repositório Institucional da Universidade de Aveiro > CIDMA - Centro de Investigação e Desenvolvimento em Matemática e Aplicações > CIDMA - Artigos >
 Edge perturbation on graphs with clusters: Adjacency, Laplacian and signless Laplacian eigenvalues
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/16521

title: Edge perturbation on graphs with clusters: Adjacency, Laplacian and signless Laplacian eigenvalues
authors: Cardoso, Domingos M.
Rojo, Oscar
keywords: Adjacency, Laplacian and signless Laplacian spectra of graphs
Graph cluste
Algebraic connectivity
Laplacian index
Adjacency index
issue date: Jan-2017
publisher: Elsevier
abstract: 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), where C is a set of cardinality |C| =c ≥2 of pairwise co-neighbor vertices sharing the same set S of s neighbors. Assuming that the graph G has k≥1 clusters (C_1, S_1), ..., (C_k, S_k), consider a family of k graphs H_1, ..., H_k and the graph G(H_1, ..., H_k) which is obtained from G after adding the edges of the graphs H_1, ..., H_ k whose vertex set of each H_j is identified with C_j, for j=1, ..., k. The Laplacian eigenvalues of G(H_1, ..., H_k)remain the same, independently of the graphs H_1, ..., H_k, with the exception of |C_1| +···+|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 H_1, ..., 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_1, ..., H_k) remain the same, independently of the graphs H_1, ..., H_k.
URI: http://hdl.handle.net/10773/16521
ISSN: 0024-3795
publisher version/DOI: http://dx.doi.org/10.1016/j.laa.2016.09.031
source: Linear Algebra and its Applications
appears in collectionsCIDMA - Artigos

files in this item

file description sizeformat
1-s2.0-S002437951630430X-main.pdf327.2 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2