TY - JOUR

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

AU - Kim, Jaehoon

AU - Kostochka, Alexandr V.

AU - O, Suil

AU - Shi, Yongtang

AU - Wang, Zhiwen

N1 - Funding Information:
Research supported by the POSCO Science Fellowship of POSCO TJ Park Foundation.Research of this author is supported in part by NSF RTG Grant DMS-1937241 and NSF Grant DMS-2153507.Research supported by NRF Grants NRF-2020R1F1A1A01048226, NRF-2021K2A9A2A06044515, and NRF-2021K2A9A2A1110161711.Research supported by NSFC Nos. 12161141006 and 12111540249.Research supported by CPSF No. 2021M691671.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2023/2

Y1 - 2023/2

N2 - 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.

AB - 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.

KW - Complete graphs

KW - Saturated graphs

KW - Spectral radius

UR - http://www.scopus.com/inward/record.url?scp=85141454727&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85141454727&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.113231

DO - 10.1016/j.disc.2022.113231

M3 - Article

AN - SCOPUS:85141454727

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 2

M1 - 113231

ER -