Packing of rigid spanning subgraphs and spanning trees

DOI10.1016/J.JCTB.2013.11.003zbMATH Open1300.05247arXiv1201.3727OpenAlexW2096249258MaRDI QIDQ401490FDOQ401490

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

Publication date: 27 August 2014

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

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.

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

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

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)

Cites Work

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

Cited In (12)

• Graph rigidity for unitarily invariant matrix norms
• 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
• Good orientations of unions of edge‐disjoint spanning trees
• Count and cofactor matroids of highly connected graphs
• Packing spanning trees and spanning 2-connected \(k\)-edge-connected essentially \((2k-1)\)-edge-connected subgraphs
• Strongly 2-connected orientations of graphs
• On packing spanning arborescences with matroid constraint
• Sufficient connectivity conditions for rigidity of symmetric frameworks
• Spectral conditions for graph rigidity in the Euclidean plane
• Spanning Rigid Subgraph Packing and Sparse Subgraph Covering

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)