The Minimum Spectral Radius of<i> tP</i>3-or<i> K</i>5-Saturated Graphs via the Number of 2-Walks

초록

For a given graph H, a graph G is H-saturated if G does not contain H as a subgraph, but for e is an element of E(G), G+e contains H as a subgraph; the spectral saturation number of H, written sat rho(n, H), is the minimum value of rho(G) in an n-vertex Hsaturated graph G. For a vertex v is an element of V(G), let l2(v) be the number of 2-walks starting from v. In this paper, when G is an n-vertex tP3- or K5-saturated connected graph, for each vertex v is an element of V(G), we prove the best lower bounds for l2(v) in terms of n and d(v), implying that sat rho(n, tP3) = rho(F) and sat rho(n, K5) = rho(Sn,4), where F is the 6-vertex graph obtained from K3 by attaching a pendant vertex to each vertex in K3 and Sn,4 is the join of K3 and (n - 3)K1.