Back to Search
Start Over
$K_{r+1}$-saturated graphs with small spectral radius
- Publication Year :
- 2020
-
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$.
- Subjects :
- 05C35, 05C50
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....5ca26f51353db47a59de49e94965044b