A note on the least (normalized) laplacian eighva;ue of signed graphs
| Autor: | Hui Shu Li, Hong Hai Li |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Tamkang Journal of Mathematics. 47:271-278 |
| ISSN: | 2073-9826 0049-2930 |
| DOI: | 10.5556/j.tkjm.47.2016.1942 |
| Popis: | Let $\Gamma=(G, \sigma)$ be a connected signed graph, and $L(\Gamma)$ be its Laplacian and $\mathcal{L}(\Gamma)$ its normalized Laplacian with eigenvalues $\lambda_1\geq \lambda_2\geq\cdots \geq \lambda_n$ and $\mu_1\geq \mu_2\geq\cdots \geq \mu_n$, respectively. It is known that a signed graph $\Gamma$ is balanced if and only if $\lambda_n=0$ (or $\mu_n=0$). We show that $\lambda_n$ and $\mu_n$ measure how much $\Gamma$ is far from being balanced by proving that \begin{align*}\mu_n(\Gamma)&\leq\min\{\frac{2\epsilon(\Gamma)}{m}, \frac{\nu(\Gamma)}{\nu(\Gamma)+\nu_1(\Gamma)}\},\\ \lambda_n(\Gamma)&\leq \min\{\lambda_1(\Gamma'): \Gamma-\Gamma'\,\,\,{is balanced}\}, \end{align*}where $\nu(\Gamma)$ (resp. $\epsilon(\Gamma)$) denotes the frustration number (resp. the frustration index) of $\Gamma$, that is the minimum number of vertices (resp. edges) to be deleted such that the signed graph is balanced. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|