| Autor: |
Cheriyan, Joseph, de Gevigney, Olivier Durand, Szigeti, Zoltán |
| Rok vydání: |
2012 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
