A note on eigenvalues of signed graphs. (English) Zbl 1496.05101
Summary: Suppose that \(\Sigma\) is a signed graph with \(n\) vertices and \(m\) edges. Let \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n\) be the eigenvalues of \(\Sigma \). A signed graph is called balanced if each of its cycles contains an even number of negative edges, and unbalanced otherwise. Let \(\omega_b\) be the balanced clique number of \(\Sigma \), which is the maximum order of a balanced complete subgraph of \(\Sigma \). In this paper, we prove that
\[
\lambda_1 \leq \sqrt{2 \frac{\omega_b - 1}{\omega_b} m}.
\] This inequality extends a conjecture of ordinary graphs, which was confirmed by V. Nikiforov [Comb. Probab. Comput. 11, No. 2, 179–189 (2002; Zbl 1005.05029)], to the signed case. In addition, we completely characterize the signed graphs with \(- 1 \leq \lambda_2 \leq 0\).
Citations:
Zbl 1005.05029References:
| [1] | Brualdi, R. A.; Hoffman, A. J., On the spectral radius of (0, 1)-matrices, Linear Algebra Appl., 65, 133-146 (1985) · Zbl 0563.15012 |
| [2] | Cvetkovic, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press: Academic Press New York · Zbl 0458.05042 |
| [3] | Cao, D.; Hong, Y., Graphs characterized by the second eigenvalue, J. Graph Theory, 17, 325-331 (1993) · Zbl 0786.05055 |
| [4] | Edwards, C.; Elphick, C., Lower bounds for the clique and the chromatic number of a graph, Discrete Appl. Math., 5, 51-64 (1983) · Zbl 0535.05029 |
| [5] | Hong, Y., Bounds of eigenvalues of graphs, Discrete Math., 123, 65-74 (1993) · Zbl 0788.05067 |
| [6] | Hong, Y.; Shu, J. L.; Fang, K. F., A sharp upper bound of the spectral radius of graphs, J. Comb. Theory, Ser. B, 81, 117-183 (2001) · Zbl 1024.05059 |
| [7] | Liu, B.; Shen, J.; Wang, X., On the largest eigenvalue of non-regular graphs, J. Comb. Theory, Ser. B, 97, 1010-1018 (2007) · Zbl 1125.05062 |
| [8] | Nikiforov, V., Some inequalities for the largest eigenvalue of a graph, Comb. Probab. Comput., 11, 179-189 (2002) · Zbl 1005.05029 |
| [9] | Stanley, R. P., A bound on the spectral radius of graphs with e edges, Linear Algebra Appl., 87, 267-269 (1987) · Zbl 0617.05045 |
| [10] | Wilf, H. S., Spectral bounds for the clique and independence numbers of graphs, J. Comb. Theory, Ser. B, 40, 113-117 (1986) · Zbl 0598.05047 |
| [11] | Wang, W.; Yan, Z.; Qian, J., Eigenvalues and chromatic number of a signed graph, Linear Algebra Appl., 619, 137-145 (2021) · Zbl 1466.05125 |
| [12] | Zhou, B.; Cho, H. H., Remarks on spectral radius and Laplacian eigenvalues of a graph, Czechoslov. Math. J., 55, 781-790 (2005) · Zbl 1081.05068 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
