Spectral analysis of (sequences of) graph matrices

We study the extreme singular values of incidence graph matrices, obtaining lower and upper estimates that are asymptotically tight. This analysis is then used for obtaining estimates on the spectral condition number of some weighted graph matrices. A short discussion on possible preconditioning strategies within interior-point methods for network flow problems is also included.