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

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 is an element of E((G) over bar), 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 is an element of V (G), Sigma(w is an element of N(v)) d(G)(w) >= (r - 2)d(v) + (r - 1)(n - r + 1), then rho(G) >= rho(S-n,S-r), where S-n,S-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. (c) 2022 Elsevier B.V. All rights reserved.