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 minG:ktextrmedge−connected maxT textrmedge−connectivity(GbackslashE(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)gelfloork/2rfloor−1. This is far from tight with respect to the best upper bound I can prove, r(k)lek−3.
No comments:
Post a Comment