A Max-Min Problem on Spectral Radius and Connectedness of Graphs

Abstract

In the past decades, many scholars have been concerned with the question of which edge-extremal problems have spectral analogues. Recently, Wang, Kang, and Xue established an interesting result on $F$-free graphs [J. Combin. Theory Ser. B 159 (2023) 20-41]. In this paper, we investigate this problem in the context of critical graphs. Let $P$ be a property defined on a family $\mathbb{G}$ of graphs. A graph $G \in \mathbb{G}$ is said to be P-critical if it satisfies $P$ but $G-e$ does not satisfy $P$ for any edge $e \in E(G)$.  Specifically, a graph is minimally $k$-(edge)-connected  if it is $k$-connected (respectively, $k$-edge-connected)  and the deletion of any edge results in a graph that is not  $k$-connected (respectively, $k$-edge-connected). A natural max-min problem is to determine the maximum spectral radius of minimally $k$-(edge)-connected graphs with $n$ vertices. In 2019, Chen and Guo [Discrete Math. 342 (2019) 2092-2099] resolved the case $k=2$. In 2021, Fan, Goryainov, and Lin [Discrete Appl. Math. 305 (2021) 154-163] determined the extremal spectral radius for minimally $3$-connected graphs. In this paper, we establish structural properties of minimally $k$-(edge)-connected graphs.  Furthermore, we solve the max-min problem for the case $k \geq 3$, demonstrating that any minimally $k$-(edge)-connected graph attaining the maximum spectral radius simultaneously achieves the maximum number of edges.