On the spectral radius of minimally 2-(edge)-connected graphs with given size

Zhenzhen Lou¹ ; Gao Min ; Qiongxiang Huang

¹Xinjiang University

The electronic journal of combinatorics, Tome 30 (2023) no. 2

Résumé

A graph is minimally $k$-connected ($k$-edge-connected) if it is $k$-connected ($k$-edge-connected) and deleting any arbitrary chosen edge always leaves a graph which is not $k$-connected ($k$-edge-connected). Let $m= \binom{d}{2}+t$, $1\leq t\leq d$ and $G_m$ be the graph obtained from the complete graph $K_d$ by adding one new vertex of degree $t$. Let $H_m$ be the graph obtained from $K_d\backslash\{e\}$ by adding one new vertex adjacent to precisely two vertices of degree $d-1$ in $K_d\backslash\{e\}$. Rowlinson [Linear Algebra Appl., 110 (1988) 43--53.] showed that $G_m$ attains the maximum spectral radius among all graphs of size $m$. This classic result indicates that $G_m$ attains the maximum spectral radius among all $2$-(edge)-connected graphs of size $m=\binom{d}{2}+t$ except $t=1$. The next year, Rowlinson [Europ. J. Combin., 10 (1989) 489--497] proved that $H_m$ attains the maximum spectral radius among all $2$-connected graphs of size $m=\binom{d}{2}+1$ ($d\geq 5$), this also indicates $H_m$ is the unique extremal graph among all $2$-connected graphs of size $m=\binom{d}{2}+1$ ($d\geq 5$). Observe that neither $G_m$ nor $H_m$ are minimally $2$-(edge)-connected graphs. In this paper, we determine the maximum spectral radius for the minimally $2$-connected ($2$-edge-connected) graphs of given size; moreover, the corresponding extremal graphs are also characterized.

Détail

DOI : 10.37236/11219

Classification : 05C50, 05C75, 05C40, 05C12, 05C35
Mots-clés : maximum spectral radius, \(2\)-connected graphs