Bounds for index of a modified graph
Bo Zhou
Discussiones Mathematicae Graph Theory, Tome 24 (2004), p. 213-221 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

If a graph is connected then the largest eigenvalue (i.e., index) generally changes (decreases or increases) if some local modifications are performed. In this paper two types of modifications are considered: (i) for a fixed vertex, t edges incident with it are deleted, while s new edges incident with it are inserted; (ii) for two non-adjacent vertices, t edges incident with one vertex are deleted, while s new edges incident with the other vertex are inserted. Within each case, we provide lower and upper bounds for the indices of the modified graphs, and then give some sufficient conditions for the index to decrease or increase when a graph is modified as above.

Publié le : 2004-01-01
EUDML-ID : urn:eudml:doc:270543 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1226,
     author = {Bo Zhou},
     title = {Bounds for index of a modified graph},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {24},
     year = {2004},
     pages = {213-221},
     zbl = {1064.05102},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1226}
}

Bo Zhou. Bounds for index of a modified graph. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 213-221. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1226/

[000] [1] D. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of graphs (Cambridge University Press, Cambridge, 1997). | Zbl 0878.05057

[001] [2] C. Maas, Perturbation results for adjacency spectrum of a graph, Z. Angew. Math. Mech. 67 (1987) 428-430.

[002] [3] P. Rowlinson, On angles and perturbations of graphs, Bull. London Math. Soc. 20 (1988) 193-197, doi: 10.1112/blms/20.3.193. | Zbl 0644.05038

[003] [4] P. Rowlinson, More on graph perturbations, Bull. London Math. Soc. 22 (1990) 209-216, doi: 10.1112/blms/22.3.209. | Zbl 0711.05034

[004] [5] W. Weinstein and W. Stenger, Methods of intermediate problems of eigenvalues (Academic Press, New York, 1972). | Zbl 0291.49034

[005] [6] B. Zhou, The changes in indices of modified graphs, Linear Algebra Appl. 356 (2002) 95-101, doi: 10.1016/S0024-3795(02)00321-X. | Zbl 1015.05046