0
$\begingroup$

Let $G(V,E)$ be an undirekted $k$-vertex-connected, $k$-regular graph
and let $F$ be an $f$-factor of $G$ consisting of a set of $f$-vertex-connected components, $f<k$.

Question:
what is the vertex-connectivity of $G\setminus F$, is it $k-f$, resp., what is the highest lower bound on the resulting vertex-connectivity?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Make $G$ from two highly-connected pieces joined by a matching of $k$ edges. It has connectivity $k$. Now take $F$ to be a perfect matching that includes the edges of the cut. $G\setminus F$ is then disconnected. So there is no general lower bound except 0.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .