|
Published in:
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:
| AUTHOR | = | {Berg, Alex and Jord{\'a}n, Tibor}, |
| TITLE | = | {Sparse certificates and removable cycles in $l$-mixed $p$-connected graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2004}, |
| NUMBER | = | {TR-2004-04} |