Geodesic
Graphs with Clusters Perturbed by Regular Graphs—Aα-Spectrum and Applications
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 451-466.

Voir la notice de l'article provenant de la source Library of Science

Given a graph G, its adjacency matrix A(G) and its diagonal matrix of vertex degrees D(G), consider the matrix Aα(G) = αD(G) + (1 − α)A(G), where α ∈ [0, 1). The Aα -spectrum of G is the multiset of eigenvalues of Aα(G) and these eigenvalues are the α-eigenvalues of G. A cluster in G is a pair of vertex subsets (C, S), where C is a set of cardinality |C| ≥ 2 of pairwise co-neighbor vertices sharing the same set S of |S| neighbors. Assuming that G is connected and it has a cluster (C, S), G(H) is obtained from G and an r-regular graph H of order |C| by identifying its vertices with the vertices in C, eigenvalues of Aα(G) and Aα(G(H)) are deduced and if Aα(H) is positive semidefinite, then the i-th eigenvalue of Aα(G(H)) is greater than or equal to i-th eigenvalue of Aα(G). These results are extended to graphs with several pairwise disjoint clusters (C1, S1), . . ., (Ck, Sk). As an application, the effect on the energy, α-Estrada index and α-index of a graph G with clusters when the edges of regular graphs are added to G are analyzed. Finally, the Aα-spectrum of the corona product G ◦ H of a connected graph G and a regular graph H is determined.
Keywords: cluster, convex combination of matrices, corona product of graphs, Aα-spectrum 
@article{DMGT_2020_40_2_a6,
     author = {Cardoso, Domingos M. and Past\'en, Germain and Rojo, Oscar},
     title = {Graphs with {Clusters} {Perturbed} by {Regular} {Graphs{\textemdash}A\protect\textsubscript{\ensuremath{\alpha}}-Spectrum} and {Applications}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {451--466},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a6/}
}
TY  - JOUR
AU  - Cardoso, Domingos M.
AU  - Pastén, Germain
AU  - Rojo, Oscar
TI  - Graphs with Clusters Perturbed by Regular Graphs—Aα-Spectrum and Applications
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 451
EP  - 466
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a6/
LA  - en
ID  - DMGT_2020_40_2_a6
ER  - 
%0 Journal Article
%A Cardoso, Domingos M.
%A Pastén, Germain
%A Rojo, Oscar
%T Graphs with Clusters Perturbed by Regular Graphs—Aα-Spectrum and Applications
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 451-466
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a6/
%G en
%F DMGT_2020_40_2_a6
Cardoso, Domingos M.; Pastén, Germain; Rojo, Oscar. Graphs with Clusters Perturbed by Regular Graphs—Aα-Spectrum and Applications. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 451-466. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a6/

[1] N.M.M. Abreu, D.M. Cardoso, E.A. Martins, M. Robbiano and B. San Martín, On the Laplacian and signless Laplacian spectrum of a graph with k pairwise co-neighbor vertices, Linear Algebra Appl. 437 (2012) 2308–2316. doi:10.1016/j.laa.2012.05.013

[2] S. Barik, S. Pati and B.K. Sarma, The spectrum of the corona of two graphs, SIAM J. Discrete Math. 21 (2007) 47–56. doi:10.1137/050624029

[3] A. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, 2012). doi:10.1007/978-1-4614-1939-6

[4] D.M. Cardoso, G. Pastén and O. Rojo, On the multiplicity of α as an eigenvalue of Aα(G) of graphs with pendant vertices, Linear Algebra Appl. 552 (2018) 52–70. doi:10.1016/j.laa.2018.04.013

[5] D.M. Cardoso and O. Rojo, Edge perturbation on graphs with clusters: Adjacency, Laplacian and signless Laplacian eigenvalues, Linear Algebra Appl. 512 (2017) 113–128. doi:10.1016/j.laa.2016.09.031

[6] D. Cvetković, P. Rowlinson and S.K. Simić, Signless Laplacian of finite graphs, Linear Algebra Appl. 423 (2007) 155–171. doi:10.1016/j.laa.2007.01.009

[7] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298–305.

[8] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970) 322–325. doi:10.1007/BF01844162

[9] J.-M. Guo, The effect on the Laplacian spectral radius of a graph by adding or grafting edges, Linear Algebra Appl. 413 (2006) 59–71. doi:10.1016/j.laa.2005.08.002

[10] R. Horn and C. Johnson, Matrix Analysis (Cambridge University Press, Cambridge, 1985). doi:10.1017/CBO9780511810817

[11] R. Merris, Laplacian matrices of graphs: A survey, Linear Algebra Appl. 197–198 (1994) 143–176. doi:10.1016/0024-3795(94)90486-3

[12] V. Nikiforov, The energy of graphs and matrices, J. Math. Anal. Appl. 326 (2007) 1472–1475. doi:10.1016/j.jmaa.2006.03.072

[13] V. Nikiforov, Merging the A- and Q-spectral theories, Appl. Anal. Discrete Math. 11 (2017) 81–107. doi:10.2298/AADM1701081N

[14] V. Nikiforov and O. Rojo, A note on the positive semidefiniteness of Aα(G), Linear Algebra Appl. 519 (2017) 156–163. doi:10.1016/j.laa.2016.12.042

[15] G. Pastén and O. Rojo, Laplacian spectrum, Laplacian-energy-like invariant, and Kirchho index of graphs constructed by adding edges on pendent vertices, MATCH Commun. Math. Comput. Chem. 73 (2015) 27–40.

[16] O. Rojo, Effects on the energy and estrada indices by adding edges among pendent vertices, MATCH Commun. Math. Comput. Chem. 74 (2015) 343–358.

[17] J.Y. Shao, J.M. Guo and H.Y. Shan, The ordering of trees and connected graphs by algebraic connectivity, Linear Algebra Appl. 428 (2008) 1421–1438. doi:10.1016/j.laa.2007.08.031

[18] W. So, Commutativity and spectra of Hermitian matrices, Linear Algebra Appl. 212–213 (1994) 121–129. doi:10.1016/0024-3795(94)90399-9