Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ and $G$ be ordered non-increasingly as $\lambda_1\ge \lambda_2\ge\cdots\ge\lambda_n>0$ and $\mu_1\ge \mu_2\ge\cdots\ge\mu_n=0$, respectively. Then can we prove that $\lvert \lambda_i-\mu_i\rvert\le 2\sqrt{n-2}$ for $i=2,\cdots,n-1$? (Please focus on the values of $i$). Recall that the Laplacian matrices for the signed graph is $L(\Sigma)=D(G)-A(\Sigma)$ where $D(G)$ is the diagonal matrix of the degrees of the vertices and $A(\Sigma)$ is the adjacency matrix. Also note that $G$ can be taken as a balanced signed graph with its edge signs as all positive ones.
5
-
$\begingroup$ I might be misunderstanding the definition of the signings and how you're defining the signed Laplacians, but if $G$ is the complete graph on $n$ vertices, and $\sigma\equiv -1$, then isn't $\lambda_1(\Sigma)=2n-2$ while $\lambda_1(G)=n$? $\endgroup$– Jason GaitondeCommented Feb 20, 2023 at 20:08
-
$\begingroup$ @ Jason You are right. Sorry for taking $i$ from 1 to n-1. It must be from 2 to n-1 instead. I have edited the question accordingly $\endgroup$– shahulhameedCommented Feb 21, 2023 at 1:43
-
$\begingroup$ So what happens if you just take the disjoint union of complete graphs on $n/2$ nodes and take $\sigma \equiv -1$? I doubt you can generically do better than what you can get from the Wielandt-Hoffman inequalities. (Also, I would prefer not to get emails about MO questions unless it's really important...) $\endgroup$– Jason GaitondeCommented Feb 24, 2023 at 17:28
-
$\begingroup$ @Jason Sorry again. My underlying graph $G $ is connected. $\endgroup$– shahulhameedCommented Feb 25, 2023 at 18:44
-
$\begingroup$ Okay, so just add a single edge between the clusters. This changes the eigenvalues by at most 2. $\endgroup$– Jason GaitondeCommented Feb 25, 2023 at 20:18
Add a comment
|