Premium
A characterization of the smallest eigenvalue of a graph
Author(s) -
Desai Madhav,
Rao Vasant
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180210
Subject(s) - adjacency matrix , combinatorics , mathematics , bipartite graph , eigenvalues and eigenvectors , graph energy , discrete mathematics , complete bipartite graph , bounded function , graph , graph power , line graph , mathematical analysis , physics , quantum mechanics
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.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.