کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656878 | 1632988 | 2014 | 9 صفحه PDF | دانلود رایگان |
We prove that every (6k+2ℓ,2k)(6k+2ℓ,2k)-connected simple graph contains k rigid and ℓ connected edge-disjoint spanning subgraphs.This implies a theorem of Jackson and Jordán [7] providing a sufficient condition for the rigidity of a graph and a theorem of Jordán [8] on the packing of rigid spanning subgraphs. Both these results generalize the classic result of Lovász and Yemini [10] saying that every 6-connected graph is rigid. Our approach provides a transparent proof for this theorem.Our result also gives two improved upper bounds on the connectivity of graphs that have interesting properties: (1) in every 8-connected graph there exists a packing of a spanning tree and a 2-connected spanning subgraph; (2) every 14-connected graph has a 2-connected orientation.
Journal: Journal of Combinatorial Theory, Series B - Volume 105, March 2014, Pages 17–25