Spectral radius of perturbed bipartite graphs

Question

I am looking into how perturbation(s) on a bipartite graph affect its spectrum (specifically its spectral radius or largest eigenvalue). Actually, I'm not exactly looking into bipartite but my simplest case can be reduced to a bipartite representation explained below.

Say I have two sets of nodes ${U,V}$. Let $0_{n}$ be an $n\times n$-zero matrix and $B_n$ be a symmetric $(0,1)$-matrix denoting the links interconnecting the two sets of nodes in $U$ and $V$, then I represent the system as the following form:

$$ A=\left( \begin{array}{cc} 0_{n} & B_n \\ B_n^{T} & 0_{n} \end{array} \right) .$$

Hence, $A$ is a symmetric matrix of order $2n$, ($B^T$ denotes the transpose of the matrix $B$).

If $B$ is to be perturbed (removal / addition of a link), how will the spectrum of $A$ change? I believe such problem should have been investigated before. Hence, I would appreciate pointers to resources to any previous work looking into such problem. Any bounds or properties would be helpful. My preliminary search points to perturbation theory which I'm not familiar. So, even some more elementary resources would be appreciated as well.

So far, I have found a couple of papers that estimate the change of spectral radius for general matrices:

[1] J. G. Restrepo, E. Ott, and B. R. Hunt, Phys. Rev. Lett. 97, 094102 (2006).

[2] A. Milanese, J. Sun, and T. Nishikawa, Phys. Rev. E 81, 046112, (2010).

I wonder if there's other results / works such as above which is specific to the perturbations of bipartite graph matrix that I'm studying here.

Also appreciated is pointers to extension of similar problem to $m$-partite graphs.

Answer 1

There are a lot of work in this direction. For an updated (and also very interesting) book, you can see:

"inequalities for graph eigenvalues" by Zoran Stanić.

Especially, you can see the chapter two of this book which has a lot of inequalities that are useful for your question. For example, for most $r$-regular graphs we have: $$\lambda_1(G+e)-\lambda_1(G)=\Theta(\frac{1}{n}).$$

Also, it contains many inequalities (especially for bipartite graphs) which you can use them for your defined perturbation(s).

You can see also the paper:

"Decreasing the spectral radius of a graph by link removals" by P. V. Mieghem and et all.

By searching in google, you can find many new other things.