Sufficient conditions for maximally edge-connected and super-edge-connected

Document Type : Original paper


1 RWTH Aachen University

2 Anhui University of Finance and Economics


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. Examples will demonstrate that our conditions are sharp.\
noindent {bf Keywords:} Edge-connectivity; Maximally edge-connected graphs; Super-edge-connected


Main Subjects