Basic subgraphs and graph spectra.
Mark N. Ellingham · 1993
mne~athena.cas.vanderbilt.edu Every symmetric matrix has an invertible principal submatrix whose rank is equal to that of the whole matrix. We explore some of the implications of this result for graph spectra. U sing the same symbol for a graph and its adjacency matrix, we say that a graph G is A-invertible if G- AI is invertible, and the A-rank of G is the rank of G- AI. A A-basic subgraph of G is an induced A-invertible subgraph H of the same A-rank as G. Using A-basic subgraphs, we prove that if A 1:. {O,-I} then the set of graphs of a given A-rank is finite; this can be extended to A = 0 and A =-1 by excluding graphs with what we call duplicate and coduplicate vertices respectively. We give an algorithm to construct the graphs of a given A-rank. We show how O-basic sub graphs can be used to calculate ranks of graphs, using as an example graphs obtained by adding two vertices to a complete graph. We examine some properties of maxima/reduced graphs, graphs which occur in characterising the graphs of a given rank, and construct some infinite families of such graphs. 1.