ROOTED-TREE DECOMPOSITIONS WITH MATROID CONSTRAINTS AND THE INFINITESIMAL RIGIDITY OP FRAMEWORKS WITH BOUNDARIES

摘要

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 that we are given a graph G = (V, E), a multiset R = {r_1,... ,r_t} of vertices in V, and a matroid 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),... ,Gt = (V_t,T_t) such that (ⅰ) for each i, G_i is a tree with r_i ∈ V_i, and (ⅱ) for each v ∈ V, the multiset {r_1 ∈ R ∣ v ∈ V_i} is a base of M. If 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 nongeneric "boundary," which extend classical the Laman's theorem for generic 2-rigidity of bar-joint frameworks and Tay's theorem for generic d-rigidity of body-bar frameworks.