The Effect of Adding an Edge on the Laplacian of a Weighted Digraph

Question

Let $G$ be a weighted digraph with Laplacian $L:=D-A$, where $D$ is the degree matrix and $A$ is the incidence matrix. Is there any result on the behavior of the eigenvalues of $L$ when we add an edge to the graph? Any reference or response is greatly appreciated. Thanks.

Answer 1

Except for some specific case where adding an edge gives you a specific graph or graph property (complete, bipartite, connected,...), I would advise you to look at this paper, and the sources.

They include lots of results on Laplacian (normalized or not), including some sort of interlacing theorems.

Answer 2

I did some research on this matter. However, we only investigated the addition of edges with small weights (resp. increasing the weight of an existing edge). You can have a look at section 3.2 in the following arXiv manuscript

https://arxiv.org/abs/1711.08909

Basically, our approach in the first article relies on the following well known perturbation formula for eigenvalues:

Let $\lambda$ be a simple eigenvalue of $L\in\mathbb{R}^{N\times N}$ with corresponding left and right eigenvectors $u,v$ and let $\tilde{L}\in\mathbb{R}^{n\times n}$. Then, for $\varepsilon$ small enough there exists a smooth family $\lambda\left(\varepsilon\right)$ of simple eigenvalues of $L+\varepsilon\tilde{L}$ with $\lambda\left(0\right)=\lambda$ and \begin{equation} \lambda^{\prime}\left(0\right)=\frac{u\tilde{L}v}{u\cdot v}.\label{eq:Eigenv_Pert} \end{equation}

I should warn you that we only consider perturbations on cutsets in weakly connected digraphs. The question is much more involved if your underlying graph is strongly connected.

Also, I am not aware of a combinatorial approach to this problem - that is an approach feasible for the addition of edges with non-small weights.