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


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
Issue number11
StatePublished - Nov 2020


  • Complete graphs
  • Saturated graphs
  • Spectral radius

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this