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.