Publication date
December 1978
DOI Publisher
Published by Elsevier B.V. ISSN
0012-365XAbstract
AbstractA 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 edgem-connectivity
Add to ORKG