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

DOI10.1137/110846944zbMATH Open1268.05160arXiv1109.0787OpenAlexW2962695452MaRDI QIDQ5300488FDOQ5300488

Authors: Naoki Katoh, Shin-Ichi Tanigawa 

Publication date: 27 June 2013

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

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.

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

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

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)

Cited In (14)

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

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)