zbMATH — the first resource for mathematics

A characterization of the smallest eigenvalue of a graph. (English) Zbl 0792.05096
Summary: It is well known that the smallest eigenvalue of the adjacency matrix of a connected \(d\)-regular graph is at least \(-d\) and is strictly greater than \(-d\) if the graph is not bipartite. More generally, for any connected graph \(G=(V,E)\), consider the matrix \(Q=D+A\) where \(D\) is the diagonal matrix of degrees in the graph \(G\) and \(A\) is the adjacency matrix of \(G\). Then \(Q\) is positive semidefinite, and the smallest eigenvalue of \(Q\) is 0 if and only if \(G\) is bipartite. We will study the separation of this eigenvalue from 0 in terms of the following measure of nonbipartiteness of \(G\). For any \(S \subseteq V\), we denote by \(e_{\min} (S)\) the minimum number of edges that need to be removed from the induced subgraph on \(S\) to make it bipartite. Also, we denote by \(\text{cut} (S)\) the set of edges with one end in \(S\) and the other in \(V-S\). We define the parameter \(\psi\) as \[ \psi=\min_{S \subseteq V} {e_{\min} (S)+| \text{cut} (S) | \over | S |}. \] The parameter \(\psi\) is a measure of the nonbipartiteness of the graph \(G\). We will show that the smallest eigenvalue of \(Q\) is bounded above and below by functions of \(\psi\). For \(d\)-regular graphs, this characterizes the separation of the smallest eigenvalue of the adjacency matrix from \(- d\). These results can be easily extended to weighted graphs.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI Link
[1] D. Aldous On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing Prob. Engin. Inform. Sci. 1987 33 46 · Zbl 1133.60327
[2] Alon, Eigenvalues and expanders, Combinatorica. 6 pp 83– (1986) · Zbl 0661.05053
[3] Cvetkovic, Spectra of Graphs (1980)
[4] M. P. Desai An eigenvalue based approach to the finite time behavior of simulated annealing 1991
[5] P. Diaconis D. Stroock Geometic bounds for eigenvalues of Markov chains 1990
[6] Fiedler, A quanitative extension of the Perron-Frobenius theorem for doubly stochastic matrices, Czech. Math. J. 25 (100) pp 339– (1975) · Zbl 0322.15021
[7] Lawler, Bounds on the L2 spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality, Trans. Am. Math. Soc. 309 pp 557– (1988) · Zbl 0716.60073
[8] B. Mohar The Laplacian spectrum of graphs 1988
[9] Senata, Nonnegative Matrices and Markov Chains (1980)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.