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 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 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.