Packing of Rigid Spanning Subgraphs and Spanning Trees
classification
💻 cs.DM
math.CO
keywords
connectedspanningeverygraphrigidsubgraphsjordpacking
read the original abstract
We prove that every (6k + 2l, 2k)-connected simple graph contains k rigid and l connected edge-disjoint spanning subgraphs. This implies a theorem of Jackson and Jord\'an [4] and a theorem of Jord\'an [6] on packing of rigid spanning subgraphs. Both these results are generalizations of the classical result of Lov\'asz and Yemini [9] saying that every 6-connected graph is rigid for which our approach provides a transparent proof. Our result also gives two improved upper bounds on the connectivity of graphs that have interesting properties: (1) every 8-connected graph packs a spanning tree and a 2-connected spanning subgraph; (2) every 14-connected graph has a 2-connected orientation.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.