Employing star complements in search for graphs with fixed rank

Abstract

A star complement in a graph G of order n is an induced subgraph H of order t, such that μ is an eigenvalue of multiplicity n−t of G, but not an eigenvalue of H. We use an idea of Torgašev to develop an algorithm based on star complements to characterize graphs with given rank (i.e., the number of non-zero eigenvalues of the adjacency matrix) or given number of eigenvalues distinct from −1. As a demonstration, we re-prove some known results concerning graphs with a comparatively small rank. By the same method, we characterize graphs having at most 6 eigenvalues distinct from −1. Comparisons with existing results are provided.