A note on the least (normalized) laplacian eighva;ue of signed graphs

Authors

  • Hui Shu Li
  • Hong Hai Li

DOI:

https://doi.org/10.5556/j.tkjm.47.2016.1942

Keywords:

signed graph, Laplacian, eigenvalues, balancedness

Abstract

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.

Author Biography

Hong Hai Li

College of Mathematics and Information Science, Jiangxi Normal University, Nanchang, JiangXi, 330022, People’s Republic of China.

References

F. M. Atay and H. Tuncel, On the spectrum of normalized Laplacian for signed graphs: Interlacing, contraction, and replication, Lin. Algebra Appl., 442(2014), 165--177.

F. Belardo, Balancedness and the least eigenvalue of Laplacian of signed graphs, Lin. Algebra Appl., 446(2014), 133--147.

F. Belardoa and S. K. Simic, On the Laplacian coefficients of signed graphs, Lin. Algebra Appl., 475(2015), 94--113.

D. Cartwright and F. Harary, Structural balance: A generalization of heider's theory, Psychological Review, 63(1956), 277--293.

S. Fallat and Y. Fan, Bipartiteness and the least eigenvalue of signless Laplacian of graphs, Lin. Algebra Appl., 436 (2012), 3254--3267.

R. Figueiredo and Y. Frota, The maximum balanced subgraph of a signed graph: Applications and solution approaches, European Journal of Operational Research, 236(2014), 473--487.

K. A. Germina, S. Hameed and K. T. Zaslavsky, On products and line graphs of signed graphs, their eigenvalues and energy, Lin. Algebra Appl., 435(2011),2432--2450.

G. Greaves, J. Koolen, A. Munemasa, Y. Sano and T. Taniguchi, Edge-signed graphs with smallest eigenvalue greater than $-2$, Journal of Combinatorial Theory, Series B, 110(2015), 90--111.

F. Heider, Attitudes and cognitive organization, Journal of Psychology, 21(1946), 107--112.

R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985.

Y. Hou, J. Li and Y. Pan, On the Laplacian eigenvalues of signed graphs, Linear and Multilinear Alg., 51(2003),21--30.

Y. Hou, Bounds for the least Laplacian eigenvalues of a signed graphs, Acta Mathematica Sinica (Engl. Ser.), 21(2005), 955--960.

H. Li and J. Li, An upper bound on the Laplacian spectral radius of the signed graphs, Discuss. Math. Graph Theory, 28(2008),345--359.

H. Li and J. Li, Note on the normalized Laplacian eigenvalues of signed, Australasian Journal of Combinatorics, 44(2009),153--162.

Y. Liu and J. Shen, The $($normalized$)$ Laplacian eigenvalue of signed graphs,Taiwanese Journal of Mathematics, in press.

Y. Tan and Y. Fan, On edge singularity and eigenvectors of mixed graphs, Acta Mathematica Sinica (Engl. Ser.), 24(2008), 139--146.

T. Zaslavsky, Signed graphs, Discrete Appl. Math.,4(1982), 47--74.

X. Zhang and R. Luo, The Laplacian eigenvalues of mixed graphs, Lin. Algebra Appl., 362(2003), 109--119.

X. Zhang, Two sharp upper bounds for the Laplacian eigenvalues, Linear Algebra Appl., 376(2004), 207--213.

Downloads

Published

2016-09-30

How to Cite

Li, H. S., & Li, H. H. (2016). A note on the least (normalized) laplacian eighva;ue of signed graphs. Tamkang Journal of Mathematics, 47(3), 271-278. https://doi.org/10.5556/j.tkjm.47.2016.1942

Issue

Section

Papers