2
$\begingroup$
  1. Does there exist a function $f: \mathbf{N} \to \mathbf{N}$ such that every $f(k)$-vertex-connected graph $G$ can have its edges partitioned into two spanning subgraphs $G_1$, $G_2$ such that both of them are $k$-vertex-connected?
  2. If so, can $f(k)$ be chosen linear in $k$?

For the record, I know the answer to both questions is "yes" when we ask for edge-connectivity instead. We may take $f(k) = 4k$. Every $4k$-edge-connected graph has $2k$ disjoint spanning trees (see, e.g. here). We define edge-disjoint subgraphs $G_1$, $G_2$ of $G$ such that each $G_i$ contains at least $k$ of the spanning trees; and we assign every remaining edge arbitrarily either to $G_1$ or $G_2$. Since each $G_i$ has at least $k$ disjoint spanning trees, it must be $k$-edge-connected.

Update: An open conjecture due to Kriesell states that there exists a function $f(k)$ such that every $f(k)$-vertex-connected graph has a spanning tree whose removal gives a $k$-vertex-connected graph. This is only known to be true for $k \leq 2$. That is, in general it is not even known how to decompose highly connected graphs into a $1$-connected and a $k$-connected spanning graphs; let alone two $k$-connected spanning subgraphs. So my question, if true, is an open problem. But it is still possible that my question might be answered in the negative with a simple counterexample, which would also be interesting.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.