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 language | English (US) |
|---|---|
| Article number | 113231 |
| Journal | Discrete Mathematics |
| Volume | 346 |
| Issue number | 2 |
| DOIs | |
| State | Published - 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
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS