A max-min problem on spectral radius and connectedness of graphs

Zhenzhen Lou ; Changxiang He¹

¹University of Shanghai for Science and Technology

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

Résumé

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.

Détail

DOI : 10.37236/12747

Classification : 05C50, 05C75, 05C40
Mots-clés : minimally \(k\)-(edge)-connected graphs, maximal spectral radius