DMGT

Discussiones Mathematicae Graph Theory 24(2) (2004) 213-221
DOI: https://doi.org/10.7151/dmgt.1226

BOUNDS FOR INDEX OF A MODIFIED GRAPH

Bo Zhou

Department of Mathematics
South China Normal University
Guangzhou 510631, P.R. China
e-mail: zhoubo@scnu.edu.cn

Abstract

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.

Keywords: graph, eigenvalue, principal eigenvector.

2000 Mathematics Subject Classification: 05C50, 15A42.

References

[1]	D. Cvetković, P. Rowlinson and S. Simić, Eigenspaces of graphs (Cambridge University Press, Cambridge, 1997).
[2]	C. Maas, Perturbation results for adjacency spectrum of a graph, Z. Angew. Math. Mech. 67 (1987) 428-430.
[3]	P. Rowlinson, On angles and perturbations of graphs, Bull. London Math. Soc. 20 (1988) 193-197, doi: 10.1112/blms/20.3.193.
[4]	P. Rowlinson, More on graph perturbations, Bull. London Math. Soc. 22 (1990) 209-216, doi: 10.1112/blms/22.3.209.
[5]	W. Weinstein and W. Stenger, Methods of intermediate problems of eigenvalues (Academic Press, New York, 1972).
[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.

Received 24 June 2002
Revised 1 March 2003