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 - 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.
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
SN - 0012-365X
VL - 346
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 2
M1 - 113231
ER -