Geodesic
On the Displacement of Eigenvalues When Removing a Twin Vertex
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 435-450.

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

Twin vertices of a graph have the same open neighbourhood. If they are not adjacent, then they are called duplicates and contribute the eigenvalue zero to the adjacency matrix. Otherwise they are termed co-duplicates, when they contribute −1 as an eigenvalue of the adjacency matrix. On removing a twin vertex from a graph, the spectrum of the adjacency matrix does not only lose the eigenvalue 0 or −1. The perturbation sends a rippling effect to the spectrum. The simple eigenvalues are displaced. We obtain a closed formula for the characteristic polynomial of a graph with twin vertices in terms of two polynomials associated with the perturbed graph. These are used to obtain estimates of the displacements in the spectrum caused by the perturbation.
Mots-clés : eigenvalues, perturbations, duplicate and co-duplicate vertices, threshold graph, nested split graph 
@article{DMGT_2020_40_2_a5,
     author = {Briffa, Johann A. and Sciriha, Irene},
     title = {On the {Displacement} of {Eigenvalues} {When} {Removing} a {Twin} {Vertex}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {435--450},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2020_40_2_a5/}
}
TY  - JOUR
AU  - Briffa, Johann A.
AU  - Sciriha, Irene
TI  - On the Displacement of Eigenvalues When Removing a Twin Vertex
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 435
EP  - 450
VL  - 40
IS  - 2
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2020_40_2_a5/
LA  - en
ID  - DMGT_2020_40_2_a5
ER  - 
%0 Journal Article
%A Briffa, Johann A.
%A Sciriha, Irene
%T On the Displacement of Eigenvalues When Removing a Twin Vertex
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 435-450
%V 40
%N 2
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2020_40_2_a5/
%G en
%F DMGT_2020_40_2_a5
Briffa, Johann A.; Sciriha, Irene. On the Displacement of Eigenvalues When Removing a Twin Vertex. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 435-450. https://geodesic-test.mathdoc.fr/item/DMGT_2020_40_2_a5/

[1] D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2001). doi:10.1017/CBO9780511801518

[2] C.E. Fröberg, Introduction to Numerical Analysis (Addison-Wesley Publishing Company, MA, 1965).

[3] W.H. Haemers, Eigenvalue Techniques in Design and Graph Theory, Ph.D. Thesis (Stichting Mathematisch Centrum, Amsterdam, 1979). doi:10.6100/IR41103

[4] W.H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226–228 (1995) 593–616. doi:10.1016/0024-3795(95)00199-2

[5] F. Harary and A. Schwenk, The spectral approach to determining the number of walks in a graph, Pacific J. Math. 80 (1979) 443–449. doi:10.2140/pjm.1979.80.443

[6] E. Heilbronner, Das Kompositions-Prinzip: Eine anschauliche Methode zur elektronen-theoretischen Behandlung nicht oder niedrig symmetrischer Molekeln im Rahmen der MO-Theorie, Helvetica Chimica Acta 36 (1953) 170–188. doi:10.1002/hlca.19530360125

[7] E. Heilbronner, Molecular Orbitals in homologen Reihen mehrkerniger aromatischer Kohlenwasserstoffe: I. Die Eigenwerte von LCAO-MO’s in homologen Reihen, Helvetica Chimica Acta 37 (1954) 921–935. doi:10.1002/hlca.19540370336

[8] E. Heilbronner, Ein graphisches Verfahren zur Faktorisierung der Säkulardeterminante aromatischer Ringsysteme im Rahmen der LCAO–MO-Theorie, Helvetica Chimica Acta 37 (1954) 913–921. doi:10.1002/hlca.19540370335

[9] E. Heilbronner, Über einen graphentheoretischen Zusammenhang zwischen dem HÜCKEL’schen MO-Verfahren und dem Formalismus der Resonanztheorie, Helvetica Chimica Acta 45 (1962) 1722–1725. doi:10.1002/hlca.19620450538

[10] E. Heilbronner, Some comments on cospectral graphs, Math. Chem. 5 (1979) 105–133.

[11] L. Lovász, Eigenvalues of graphs (2007). http://web.cs.elte.hu/lovasz/eigenvals-x.pdf

[12] M.C. Marino, I. Sciriha, S.K. Simić and D.V. Tošić, More about singular line graphs of trees, Publ. Inst. Math. (Beograd) (N.S.) 79(93) (2006) 1–12. doi:10.2298/PIM0693001M

[13] A. Mohammadian and V. Trevisan, Some spectral properties of cographs, Discrete Math. 339 (2016) 1261–1264. doi:10.1016/j.disc.2015.11.005

[14] V.R. Rosenfeld, Another form of the transmission function, J. Math. Chem. 51 (2013) 2639–2643. doi:10.1007/s10910-013-0239-3

[15] P. Rowlinson, Co-cliques and star complements in extremal strongly regular graphs, Linear Algebra Appl. 421 (2007) 157–162. doi:10.1016/j.laa.2006.04.002

[16] P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 455–471. doi:10.2298/AADM0702445R

[17] A.J. Schwenk, Computing the characteristic polynomial of a graph, in: Graphs and Combinatorics, Lecture Notes in Math. 406 (Springer, Berlin, Heidelberg, 1974) 153–172. doi:10.1007/BFb0066438

[18] I. Sciriha, J.A. Briffa and M. Debono, Fast algorithms for indices of nested split graphs approximating real complex networks, Discrete Appl. Math. 247 (2018) 152–164. doi:10.1016/j.dam.2018.03.054

[19] I. Sciriha, M. Debono, M. Borg, P. Fowler and B. Pickup, Interlacing-extremal graphs, Ars Math. Contemp. 6 (2013) 261–278. doi:10.26493/1855-3974.275.574

[20] I. Sciriha and S. Farrugia, On the spectrum of threshold graphs, ISRN Discrete Math. 2011 (2011) #108509. doi:10.5402/2011/108509

[21] W. So, Rank one perturbation and its application to the Laplacian spectrum of a graph, Linear Multilinear Algebra 46 (1999) 193–198. doi:10.1080/03081089908818613

[22] M. Thüne, Eigenvalues of Matrices and Graphs, Ph.D. Thesis (Leipzig University, Leipzig, 1979).