Chain decompositions and independent trees in 4-connected graphs

摘要

This work was motivated by the study of a multitree approach to reliability in distributed networks and by the study of non-separating paths and cycles in highly connected graphs. We first give a result on "non-separating chains" in 4-connected graphs. This result is then used to obtain a "non-separating chain decomposition" of a 4-connected graph G, and an O(|V(G)|²|E(G)|) algorithm for constructing such a decomposition. As an application of this decomposition, we show how to produce four "independent spanning trees" in a 4-connected graph in O(|V(G)|³) time.