The minimum spectral radius of Kr+1-saturated graphs

Abstract

For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e is an element of E((G) over bar), G+e contains H. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in n-vertex Kr+1-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed r and n -> infinity.