Mathematics – Combinatorics
Scientific paper
2011-09-05
Mathematics
Combinatorics
Scientific paper
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,..., r_t\}$ of vertices in $V$, and a matroid ${\cal M}$ 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),..., 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 $v\in V$, the multiset $\{r_i\in R\mid v\in V_i\}$ is a base of ${\cal M}$. If ${\cal M}$ 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.
Katoh Naoki
Tanigawa Shin-ichi
No associations
LandOfFree
Rooted-tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rooted-tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rooted-tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-449155