Spanning Rigid Subgraph Packing and Sparse Subgraph Covering

Rigidity, arising in discrete geometry, is the property of a structure that does not flex. Laman provides a combinatorial characterization of rigid graphs in the Euclidean plane, and thus rigid graphs in the Euclidean plane have applications in graph theory. We discover a sufficient partition condition of packing spanning rigid subgraphs and spanning trees. As a corollary, we show that a simple graph G contains a packing of k spanning rigid subgraphs and l spanning trees if G is $(4k+2l)$-edge-connected, and $G-Z$ is essentially $(6k+2l - 2k|Z|)$-edge-connected for every Z⊂ V(G). Thus every $(4k+2l)$-connected and essentially $(6k+2l)$-connected graph G contains a packing of k spanning rigid subgraphs and l spanning trees. Utilizing this, we show that every 6-connected and essentially 8-connected graph G contains a spanning tree T such that $G-E(T)$ is 2-connected. These improve some previous results. Sparse subgraph covering problems are also studied.