Sparse connectivity certificates via MA orderings in graphs Original Research Article

For an undirected multigraph image, let image be a positive integer weight function on V. For a positive integer k, G is called image-connected if any two vertices image remain connected after removal of any pair image of a vertex subset image and an edge subset image such that image. The image-connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a image-connected graph G, we show that a image-connected spanning subgraph of G with image edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the image-connectivity.