Let be integers. We prove that every -connected graph contains p spanning subgraphs for and q spanning trees such that all subgraphs are pairwise edge-disjoint and such that each is k-edge-connected, essentially -edge-connected, and is -edge-connected for all . This extends the well-known result of Nash-Williams and Tutte on packing spanning trees, a theorem that every 6p-connected graph contains p pairwise edge-disjoint spanning 2-connected subgraphs, and a theorem that every -connected graph contains p spanning 2-connected subgraphs and q spanning trees, which are all pairwise edge-disjoint. As an application, we improve a result on k-arc-connected orientations.
展开▼
