Maximal Spectral Radius of Minimally k k‐ (Edge) ‐Connected Graphs

ABSTRACT Minimally ‐connected graphs are the main focus of both structural and extremal graph theory. Perhaps the most heavily investigated parameter of this graph family is the number of vertices of degree . Mader proved a tight lower bound for , independent of , and the order . In 1981, inspired by matroids, Oxley discovered that in many cases, a considerably better bound can be given by using the size as a parameter. Along this line, Schmidt Tight bounds for the vertices of degree in minimally ‐connected graphs, J. Graph Theory 88 (2018) 146–153 showed that , and this bound is best possible. Another interesting problem was posed for connected graphs with fixed size: what is the maximal spectral radius of a minimally ‐(edge)‐connected graph on edges? This contribution can be traced back to Brualdi and Hoffman, who also conjectured that is the extremal graph among all connected graphs with edges, where is obtained from the complete graph by adding a new vertex of degree . This conjecture was completely solved by Rowlinson in 1988 using double eigenvector transformations. Recently, the case for was answered by Lou, Gao and Huang (2023). In this paper, we solve the problem completely, and further, for each and , the unique extremal graph is determined.