$K_{r+1}$-saturated graphs with small spectral radius

Abstract

For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e\in E(\overline{G})$, $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 $K_{r+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\to \infty$.

References in corpus (1)

• The smallest eigenvalue of K_p-free graphs

Cited by in corpus (1)

• Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph