The minimum spectral radius of Kr+1-saturated graphs

Jaehoon Kim, Seog Jin Kim, Alexandr V. Kostochka, Suil O

Research output: Contribution to journalArticlepeer-review

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 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→∞.

Original languageEnglish (US)
Article number112068
JournalDiscrete Mathematics
Volume343
Issue number11
DOIs
StatePublished - 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<sub>r+1</sub>-saturated graphs'. Together they form a unique fingerprint.

Cite this