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

Document Type: Original paper

Authors

1 RWTH Aachen University

2 Anhui University of Finance and Economics

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

Keywords

Main Subjects