- Series
- Graph Theory Seminar
- Time
- Thursday, March 8, 2018 - 1:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Alexander Hoyer – Math, GT
- Organizer
- Robin Thomas

For a graph G, a set of subtrees of G are edge-independent with
root r ∈ V(G) if, for every vertex v ∈ V(G), the paths between v and r
in each tree are edge-disjoint. A set of k such trees represent a set of
redundant
broadcasts from r which can withstand k-1 edge failures. It is easy to
see that k-edge-connectivity is a necessary condition for the existence
of a set of k edge-independent spanning trees for all possible roots.
Itai and Rodeh have conjectured that this condition
is also sufficient. This had previously been proven for k=2, 3. We
prove the case k=4 using a decomposition of the graph similar to an ear
decomposition. Joint work with Robin Thomas.