Packing of rigid spanning subgraphs and spanning trees

DOI10.1016/J.JCTB.2013.11.003MaRDI QIDQ401490zbMATH OpenOpenAlexFDO

Authors Joseph Cheriyan, Olivier Durand de Gevigney, Zoltán Szigeti

Publication date 27 August 2014

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3727

zbMATH Keywords

rigiditymatroidorientationpacking

Mathematics Subject Classification ID

Trees (05C05) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Spanning Rigid Subgraph Packing and Sparse Subgraph Covering
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Packing spanning trees and spanning 2-connected \(k\)-edge-connected essentially \((2k-1)\)-edge-connected subgraphs
• Spanning tree packing and 2-essential edge-connectivity
• Packing spanning trees in highly essentially connected graphs

Cites work

• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• scientific article; zbMATH DE number 863470 (Why is no real title available?)
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• A sufficient connectivity condition for generic rigidity in the plane
• Connected rigidity matroids and unique realizations of graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• On Generic Rigidity in the Plane
• On the Problem of Decomposing a Graph into n Connected Factors
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Simultaneous well-balanced orientations of graphs
• Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
• Two‐connected orientations of Eulerian graphs

Cited in

(15)

• Spectral conditions for graph rigidity in the Euclidean plane
• Spanning Rigid Subgraph Packing and Sparse Subgraph Covering
• Graph rigidity for unitarily invariant matrix norms
• Packing spanning trees in highly essentially connected graphs
• On orientations maximizing total arc-connectivity
• On Frank's conjecture on \(k\)-connected orientations
• Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
• Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits
• Good orientations of unions of edge‐disjoint spanning trees
• Source location with rigidity and tree packing requirements
• Count and cofactor matroids of highly connected graphs
• Strongly 2-connected orientations of graphs
• Packing spanning trees and spanning 2-connected \(k\)-edge-connected essentially \((2k-1)\)-edge-connected subgraphs
• On packing spanning arborescences with matroid constraint
• Sufficient connectivity conditions for rigidity of symmetric frameworks

This page was built for publication: Packing of rigid spanning subgraphs and spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q401490)