Abstract
We consider the following variant of the edge-augmentation problem: Given a k-edge-connected graph with no loops or multiple edges, find a smallest edge set in the complement whose addition to G results in a (k+1)-edge-connected graph. We establish the following dichotomy for this problem: If the complement of G contains a matching covering all vertices of G-degree k (and possibly more), then the complement also contains a matching whose addition to G results in a (k+1)-edge-connected graph. A smallest matching which augments the minimum degree can be found, in polynomial time, by Edmonds' matching algorithm, but it need not augment the edge-connectivity. Indeed, it is NP-hard to find a smallest edge-connectivity augmenting edge set, by a result of Tibor Jordán. On the other hand, if the complement of G contains no matching covering all vertices of G-degree k, then the complement has a minimum degree augmenting path system consisting of paths of length 1 or 2. Again we can find such a path system with as few edges as possible by Edmonds' matching algorithm. We can, in polynomial time, modify it to an edge-connectivity augmenting path system of paths of length 1 or 2 with the same number of edges, and this time it yields a smallest edge-connectivity augmenting set of edges. Combining these results, we conclude that a smallest edge-connectivity augmenting edge set in the complement of a k-regular, k-edge-connected simple graph has size n-m(G), where n is the number of vertices of G, and (m(G) is the size of a maximum matching in the complement of G. Another corollary is that the complement of every simple noncomplete graph G with n vertices has a set of at most 2n/3 edges whose addition to G results in a graph of larger edge-connectivity, with equality holding if and only the complement of G is a disjoint union of 3-cycles.
Original language | English |
---|---|
Journal | SIAM Journal on Discrete Mathematics |
Volume | 39 |
Issue number | 1 |
Pages (from-to) | 163-169 |
ISSN | 0895-4801 |
DOIs | |
Publication status | Published - 2025 |