Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
Abstract
Garamvölgyi, Jordán, Király and Villányi [{{\bf Forum Math. Pi} \textbf{13} (2025), Paper No.~e11}] posed two sharp connectivity conjectures for packing rigid spanning subgraphs: one for the equal-dimensional case and the other for the packing of a d-rigid spanning subgraph with a spanning tree. We prove a unified theorem: for arbitrary positive integers d1,…,ds, every ∑i=1sdi(di+1)-connected graph contains pairwise edge-disjoint spanning subgraphs H1,…,Hs such that Hi is di-rigid for every i. The connectivity bound is sharp whenever ∑i=1sdi(di+1)≥4. As special cases, the theorem settles both conjectures, confirms the conjecture of Garamvölgyi, Jordán and Király [{\bf J. Combin. Theory Ser. B} \textbf{166} (2024), 1--29] that every tk(k+1)-connected graph contains t pairwise edge-disjoint k-connected spanning subgraphs, and gives the sharp threshold d(d+1)+2r for packing one d-rigid spanning subgraph together with r pairwise edge-disjoint spanning trees. We also obtain two upper bounds related to Thomassen's conjecture on highly connected orientations of graphs. If f(q) is the least integer such that every f(q)-connected graph has a q-connected orientation, then f(q)≤(25q2+41q−16)/2 for every q≥3 and f(q)≤8q2+212q+1404=(8+o(1))q2 for all sufficiently large q; these two results reduce the leading coefficient in the previous quadratic bound from $320$ to 25/2 for every q≥3 and $8$ for all sufficiently large q. Compared to the bound for f(q) obtained by Garamvölgyi et al. we obtain the better bounds, not only through our tight rigidity result but also by exploiting the leftover edges when we remove two edge-disjoint spanning (sufficiently) rigid graphs.
Related
- Modulo k-orientations of highly edge-connected signed graphs
- Conformal tetrahedra and global rigidity of sphere packings in constant curvature background geometry
- Eccentric Connectivity Index of Cartesian product and Strong product of Strongly Connected Digraphs
- The stability landscape in wave-packet scattering: geometric rigidity and sharp Sobolev thresholds
- Connectivity keeping pendant extensions of paths in k-connected graphs and triangle-free graphs
BibTeX
@misc{bai2026sharp,
title = {{Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs}},
author = {Hanzhi Bai and Jørgen Bang-Jensen and Jin Yan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24463},
eprint = {2609.24463},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24463},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
AU - Hanzhi Bai
AU - Jørgen Bang-Jensen
AU - Jin Yan
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.24463
UR - https://arxiv.org/abs/2609.24463
AB - Garamvölgyi, Jordán, Király and Villányi [{{\bf Forum Math. Pi} \textbf{13} (2025), Paper No.~e11}] posed two sharp connectivity conjectures for packing rigid spanning subgraphs: one for the equal-dimensional case and the other for the packing of a d-rigid spanning subgraph with a spanning tree. We prove a unified theorem: for arbitrary positive integers d_1,…,d_s, every ∑_i=1^sd_i(d_i+1)-connected graph contains pairwise edge-disjoint spanning subgraphs H_1,…,H_s such that H_i is d_i-rigid for every i. The connectivity bound is sharp whenever ∑_i=1^sd_i(d_i+1)≥4. As special cases, the theorem settles both conjectures, confirms the conjecture of Garamvölgyi, Jordán and Király [{\bf J. Combin. Theory Ser. B} \textbf{166} (2024), 1--29] that every tk(k+1)-connected graph contains t pairwise edge-disjoint k-connected spanning subgraphs, and gives the sharp threshold d(d+1)+2r for packing one d-rigid spanning subgraph together with r pairwise edge-disjoint spanning trees. We also obtain two upper bounds related to Thomassen's conjecture on highly connected orientations of graphs. If f(q) is the least integer such that every f(q)-connected graph has a q-connected orientation, then f(q)≤(25q^2+41q−16)/2 for every q≥3 and f(q)≤8q^2+212q+1404=(8+o(1))q^2 for all sufficiently large q; these two results reduce the leading coefficient in the previous quadratic bound from $320$ to 25/2 for every q≥3 and $8$ for all sufficiently large q. Compared to the bound for f(q) obtained by Garamvölgyi et al. we obtain the better bounds, not only through our tight rigidity result but also by exploiting the leftover edges when we remove two edge-disjoint spanning (sufficiently) rigid graphs.
ER -