How to make a graph four-connected

How to make a graph four-connected

0.00 Avg rating—0 Votes
Article ID: iaor20001725
Country: Germany
Volume: 84
Issue: 3
Start Page Number: 555
End Page Number: 563
Publication Date: Jan 1999
Journal: Mathematical Programming
Authors: ,
Abstract:

Two extremal-type versions of the connectivity augmentation problem are investigated. Using ear-decomposition theorems we prove that (i) every 2-connected graph on n vertices can be made 4-connected by adding at most n new edges, and (ii) every 3-connected and 3-regular graph on n ≥ 8 vertices can be made 4-connected by adding n/2 new edges.

Reviews

Required fields are marked *. Your email address will not be published.