Eigenvalue location for chain graphs

Abstract

Chain graphs (also called double nested graphs) play an important role in the spectral graph theory since every connected bipartite graph of fixed order and size with maximal largest eigenvalue is a chain graph. In this paper, for a given chain graph G, we present an algorithmic procedure for obtaining a diagonal matrix congruent to A+xI, where A is the adjacency matrix of G and x any real number. Using this procedure we show that any chain graph has its least positive eigenvalue greater than 12, and also prove that this bound is best possible. A similar procedure for threshold graphs (also called nested split graphs) is outlined.