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

• Edge-connectivity; Maximally edge-connected graphs; Super-edge-connected graphs