14
$\begingroup$

Suppose you have a 100-edge connected graph (e.g. an infrastructure network). You want to delete the edges of a spanning tree, any spanning tree you choose (e.g. to sell a connected subnetwork). What is the most edge-connectivity you can guarantee in the remaining graph?

Formally: let $r(k)$ be $$\min_{G: k \textrm{ edge-connected}} ~~ \max_{T} ~~ \textrm{edge-connectivity}(G \backslash E(T))$$ where $T$ ranges over spanning trees of $G$, then what is $r(k)$?

I feel that in general, starting from a $k$-edge-connected graph, one should be able to leave edge-connectivity $k-o(k)$. However, the only useful bound I see so far is that "Every $2t$-edge-connected graph has $t$ spanning trees" implies $r(k) \ge \lfloor k/2 \rfloor - 1$. This is far from tight with respect to the best upper bound I can prove, $r(k) \le k-3$.

$\endgroup$
2
  • $\begingroup$ Out of curiosity, how do you prove the upper bound r(k)≤k−3? $\endgroup$ Sep 6, 2010 at 12:29
  • 1
    $\begingroup$ Take a $k$-regular $k$-edge-connected graph with no Hamiltonian path. Since it is non-Hamiltonian, the spanning tree must have degree 3 at some vertex. Thus the remainder has degree at most $k-3$ at some vertex. $\endgroup$ Sep 7, 2010 at 9:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.