A sharp lower bound for the spectral radius in K4-saturated graphs

Jaehoon Kim, Alexandr V. Kostochka, Suil O, Yongtang Shi, Zhiwen Wang

Research output: Contribution to journalArticlepeer-review

Abstract

For given graphs G and H, the 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 that if G is an n-vertex Kr+1-saturated graph such that for each vertex v∈V(G), ∑w∈N(v)dG(w)≥(r−2)d(v)+(r−1)(n−r+1), then ρ(G)≥ρ(Sn,r), where Sn,r is the graph obtained from a copy of Kr−1 with vertex set S by adding n−r+1 vertices, each of which has neighborhood S. This provides a sharp lower bound for the spectral radius in an n-vertex Kr+1-saturated graph for r=2,3, verifying a special case of a conjecture by Kim, Kim, Kostochka and O.

Original languageEnglish (US)
Article number113231
JournalDiscrete Mathematics
Volume346
Issue number2
DOIs
StatePublished - Feb 2023

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 'A sharp lower bound for the spectral radius in K4-saturated graphs'. Together they form a unique fingerprint.

Cite this