Sunday, 3 August 2008

graph theory - How much must deleting a spanning tree reduce edge-connectivity?

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$.

No comments:

Post a Comment