The Minimum Spectral Radius of $tP_3$- or $K_5$-Saturated Graphs via the Number of $2$-Walks

Abstract

For a given graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph, but for $e \in E(\overline{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 $H$-saturated graph $G$.

For a vertex $v \in V(G)$, let $l_2(v)$ be the number of $2$-walks starting from $v$. In this paper, when $G$ is an $n$-vertex $tP_3$- or $K_5$-saturated connected graph, for each vertex $v \in V(G)$, we prove the best lower bounds for $l_2(v)$ in terms of $n$ and $d(v)$, implying that $sat_{\rho}(n,tP_3)=\rho(F)$ and $sat_{\rho}(n,K_5)=\rho(S_{n,4})$, where $F$ is the $6$-vertex graph obtained from $K_3$ by attaching a pendant vertex to each vertex in $K_3$ and $S_{n,4}$ is the join of $K_3$ and $(n-3)K_1$.