TR-2004-04

Sparse certificates and removable cycles in l-mixed p-connected graphs

Alex Berg, Tibor Jordán

Published in:
Oper. Res. Lett. 33 (2005) 111-114.



Abstract

A graph G=(V,E) is called l-mixed p-connected if G-S-L is connected for all pairs S,L with S \subseteq V, L \subseteq E, and l|S|+|L|<p. This notion is a common generalisation of m-vertex-connectivity (l=1, p=m) and m-edge-connectivity (l\geq m, p=m). If p=kl then we obtain (k,l)-connectivity, introduced earlier by Kaneko and Ota, as a special case.
 
We shown that by using maximum adjacency orderings one can find sparse local certificates for l-mixed p-connectivity in linear time, provided the maximum edge multiplicity is at most l. A by-product of this result is a short proof for the existence of (and a linear time algorithm to find) a cycle C in an l-mixed p-connected graph with minimum degree at least p+2, for which G-E(C) is l-mixed p-connected. This extends a result of Mader on removable cycles in k-vertex-connected graphs.


Bibtex entry:

@techreport{egres-04-04,
AUTHOR = {Berg, Alex and Jord{\'a}n, Tibor},
TITLE = {Sparse certificates and removable cycles in $l$-mixed $p$-connected graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2004},
NUMBER = {TR-2004-04}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!