pith. sign in

arxiv: 1201.3727 · v1 · pith:QAD3XLO3new · submitted 2012-01-18 · 💻 cs.DM · math.CO

Packing of Rigid Spanning Subgraphs and Spanning Trees

classification 💻 cs.DM math.CO
keywords connectedspanningeverygraphrigidsubgraphsjordpacking
0
0 comments X
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.