Geodesic
Perturbations in a Signed Graph and its Index
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 841-852.

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

In this paper we consider the behaviour of the largest eigenvalue (also called the index) of signed graphs under small perturbations like adding a vertex, adding an edge or changing the sign of an edge. We also give a partial ordering of signed cacti with common underlying graph by their indices and demonstrate a general method for obtaining lower and upper bounds for the index. Finally, we provide our computational results related to the generation of small signed graphs.
Keywords: signed graph, switching equivalence, index, computer search 
@article{DMGT_2018_38_3_a13,
     author = {Stani\'c, Zoran},
     title = {Perturbations in a {Signed} {Graph} and its {Index}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {841--852},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a13/}
}
TY  - JOUR
AU  - Stanić, Zoran
TI  - Perturbations in a Signed Graph and its Index
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 841
EP  - 852
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a13/
LA  - en
ID  - DMGT_2018_38_3_a13
ER  - 
%0 Journal Article
%A Stanić, Zoran
%T Perturbations in a Signed Graph and its Index
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 841-852
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a13/
%G en
%F DMGT_2018_38_3_a13
Stanić, Zoran. Perturbations in a Signed Graph and its Index. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 841-852. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a13/

[1] F. Belardo, E.M. Li Marzi and S.K. Simić, Combinatorial approach for computing the characteristic polynomial of a matrix, Linear Algebra Appl. 433 (2010) 1513–1523. doi:10.1016/j.laa.2010.05.010

[2] F. Belardo and P. Petecki, Spectral characterizations of signed lollipop graphs, Linear Algebra Appl. 480 (2015) 144–167. doi:10.1016/j.laa.2015.04.022

[3] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs — Theory and Application, 3rd Edition (Johann Ambrosius Barth Verlag, Heidelberg–Leipzig, 1995).

[4] D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2010).

[5] W.H. Haemars and E. Spence, Enumeration of cospectral graphs, European J. Combin. 25 (2004) 199–211. doi:10.1016/S0195-6698(03)00100-8

[6] T. Koledin and Z. Stanić, Connected signed graphs of fixed order, size, and number of negative edges with maximal index, Linear Multilinear Algebra 65 (2017) 2187–2198. doi:10.1080/03081087.2016.1265480

[7] B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014) 94–112. doi:10.1016/j.jsc.2013.09.003

[8] G. Pólya, Kombinatorische Anzahlbestimmungen f ü r Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937) 145–254. doi:10.1007/BF02546665

[9] S.K. Simić and Z. Stanić, Polynomial reconstruction of signed graphs, Linear Algebra Appl. 501 (2016) 390–408. doi:10.1016/j.laa.2016.03.036

[10] Z. Stanić, Inequalities for Graph Eigenvalues (Cambridge University Press, Cambridge, 2015).