A characterization of the smallest eigenvalue of a graph
Authors:
- 1 March 1994
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 18 (2) , 181-194
Abstract
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 ⊆ V, we denote by emin(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 cut(S) the set of edges with one end in S and the other in V − S. We define the parameter Ψ as. magnified image The parameter Ψ 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 Ψ. 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.Keywords
This publication has 6 references indexed in Scilit:
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's InequalityTransactions of the American Mathematical Society, 1988
- Bounds on the 𝐿² spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequalityTransactions of the American Mathematical Society, 1988
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated AnnealingProbability in the Engineering and Informational Sciences, 1987
- Eigenvalues and expandersCombinatorica, 1986
- A quantitative extension of the Perron-Frobenius theorem for doubly stochastic matricesCzechoslovak Mathematical Journal, 1975