Sufficient conditions for graphs to be $k$-connected, maximally connected and super-connected

Zhen-Mu Hong, Zheng-Jiang Xia, Fuyuan Chen, Lutz Volkmann

Published 2017-08-17Version 1

Let $G$ be a connected graph with minimum degree $\delta(G)$ and vertex-connectivity $\kappa(G)$. The graph $G$ is $k$-connected if $\kappa(G)\geq k$, maximally connected if $\kappa(G) = \delta(G)$, and super-connected (or super-$\kappa$) if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we show that a connected graph or a connected triangle-free graph is $k$-connected, maximally connected or super-connected if the number of edges or the spectral radius is large enough.