ELA, Volume 6, pp. 2-10, October 1999, abstract.
Spectra of Expansion Graphs
Shmuel Friedland and Hans Schneider
Replace certain edges of a directed graph by chains and
consider the effect on the spectrum of the graph.
It is shown that the spectral radius decreases monotonically
with the expansion and that, for a strongly connected graph
that is not a single cycle, the spectral radius decreases
strictly monotonically with the expansion.
A limiting formula is given for the spectral radius of the
expanded graph when the lengths of some chains replacing
the original edges tend to infinity.
The proofs depend on the construction of auxiliary nonnegative
matrices of the same size and with the same support as the
original adjacency matrix.