Edge-Connectivity Augmentation of Simple Graphs

Kasper Skov Johansen, Eva Rotenberg, Carsten Thomassen*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

42 Downloads (Pure)

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 languageEnglish
JournalSIAM Journal on Discrete Mathematics
Volume39
Issue number1
Pages (from-to)163-169
ISSN0895-4801
DOIs
Publication statusPublished - 2025

Fingerprint

Dive into the research topics of 'Edge-Connectivity Augmentation of Simple Graphs'. Together they form a unique fingerprint.

Cite this