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

Abstract

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)\ge 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.

15 pages

Cited by in corpus (1)

• Vertex-connectivity and $Q$-index of graphs with fixed girth