2012/01/18 by Joseph Cheriyan, Cheriyan, Joseph, Olivier Durand de Gevigney +3
Computer Science · Engineering · Mathematics · #05C40 #Advanced Materials and Mechanics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Structural Analysis and Optimization #cs.DM #math.CO #msc:05C40
paper · pdf · doi:10.48550/arxiv.1201.3727
arxiv created 2012/01/18 · openalex publication_date 2012/01/18 · arxiv updated 2012/01/19 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
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án [4] and a theorem of Jordán [6] on packing of rigid spanning subgraphs. Both these results are generalizations of the classical result of Lovász 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.