On k-minimally n-edge-connected graphs

A graph is k-minimal with respect to some parameter if the removal of any j edges j<k reduces the value of that parameter by j. For k = 1 this concept is well-known; we consider multiple minimality, that is, k ? 2. We characterize all graphs which are multiply minimal with respect to connectivity or edge-connectivity. We also show that there are essentially no diagraphs which are multiply minimal with respect to diconnectivity or edge-diconnectivity. In addition, we investigate basic properties and multiple minimality for a variant of edge-connectivity which we call edge^m-connectivity.