Communications in Combinatorics and Optimization (Jan 2017)
Sufficient conditions for maximally edge-connected and super-edge-connected graphs
Abstract
Let $G$ be a connected graph with minimum degree $\delta$ and edge-connectivity $\lambda$. A graph is maximally edge-connected if $\lambda=\delta$, and it is super-edge-connected if every minimum edge-cut is trivial; that is, if every minimum edge-cut consists of edges incident with a vertex of minimum degree. In this paper, we show that a connected graph or a connected triangle-free graph is maximally edge-connected or super-edge-connected if the number of edges is large enough.
Keywords