The minimum spectral radius of \(tP_3\)- or \(K_5\)-saturated graphs via the number of \(2\)-walks

Jiangdong Ai¹ ; Pei Liu² ; Suil O³ ; Junxue Zhang¹

¹Nankai University
²Sungkyunkwan University
³The State University of New York, Korea

The electronic journal of combinatorics, Tome 32 (2025) no. 1

Résumé

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

Détail

DOI : 10.37236/12492

Classification : 05C50, 05C15, 05C60, 05C35, 15A18
Mots-clés : spectral saturation number, equitable quotient matrix of a graph