Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries

DOI10.1137/110846944zbMATH Open1268.05160OpenAlexW2962695452MaRDI QIDQ5300488FDOQ5300488

Authors Naoki Katoh, Shin-Ichi Tanigawa

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

rigidity of graphstree decompositiontree packingcount matroidsbar-joint frameworksbody-bar frameworks

Mathematics Subject Classification ID

Convex programming (90C25) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: As an extension of a classical tree-partition problem, we consider decompositions of graphs into edge-disjoint (rooted-)trees with an additional matroid constraint. Specifically, suppose we are given a graph $G=(V,E)$, a multiset $R=r1,\mathrm{...},r_t$ of vertices in $V$, and a matroid $calM$ on $R$. We prove a necessary and sufficient condition for $G$ to be decomposed into $t$ edge-disjoint subgraphs $G_1=(V_1,T_1),\mathrm{...},G_t=(V_t,T_t)$ such that (i) for each $i$, $G_i$ is a tree with $r_{i}in{V}_i$, and (ii) for each $vinV$, the multiset $r_{i}inRmidvin{V}_i$ is a base of $calM$. If $calM$ is a free matroid, this is a decomposition into $t$ edge-disjoint spanning trees; thus, our result is a proper extension of Nash-Williams' tree-partition theorem. Such a matroid constraint is motivated by combinatorial rigidity theory. As a direct application of our decomposition theorem, we present characterizations of the infinitesimal rigidity of frameworks with non-generic "boundary", which extend classical Laman's theorem for generic 2-rigidity of bar-joint frameworks and Tay's theorem for generic $d$-rigidity of body-bar frameworks.

Recommendations

• The Union of Matroids and the Rigidity of Frameworks
• On Some Problems in the Design of Plane Skeletal Structures
• Rigidity theory for matroids
• On characterizations of rigid graphs in the plane using spanning trees
• On the 2-sum in rigidity matroids

Cited in

(14)

• Rigidity of symmetric linearly constrained frameworks in the plane
• Global Rigidity of Line Constrained Frameworks
• An improved bound for the rigidity of linearly constrained frameworks
• Packing of maximal independent mixed arborescences
• Graded sparse graphs and body-length-direction frameworks
• Directed graphs, decompositions, and spatial linkages
• Polymatroid-based capacitated packing of branchings
• Point-hyperplane frameworks, slider joints, and rigidity preserving transformations
• A sufficient connectivity condition for rigidity and global rigidity of linearly constrained frameworks in \(\mathbb{R}^2\)
• Packing of arborescences with matroid constraints via matroid intersection
• On maximal independent arborescence packing
• Old and new results on packing arborescences in directed hypergraphs
• Covering intersecting bi-set families under matroid constraints
• Reachability in arborescence packings

This page was built for publication: Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries

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