## Abstract

For a graph H, a graph G is H-saturated if G does not contain H as a subgraph but for any e∈E(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→∞.

Original language | English (US) |
---|---|

Article number | 112068 |

Journal | Discrete Mathematics |

Volume | 343 |

Issue number | 11 |

DOIs | |

State | Published - Nov 2020 |

## Keywords

- Complete graphs
- Saturated graphs
- Spectral radius

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'The minimum spectral radius of K_{r+1}-saturated graphs'. Together they form a unique fingerprint.