Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653444 | European Journal of Combinatorics | 2015 | 17 Pages |
Abstract
We consider graded sparse graphs: graphs satisfying different sparsity conditions for different types of edges. We provide an inductive construction for these graphs and a decomposition into ‘graded pseudoforests’ i.e. spanning subgraphs in which each connected component contains at most one cycle and in which the edges in such a cycle are restricted by the grading. The decomposition is used to obtain combinatorial characterisations of rigidity in different types of body-length-direction frameworks. We also study graded sparse graphs from a matroid view point and derive the rank function as well as a decomposition for matroids defined by graded sparse graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Bill Jackson, Viet Hang Nguyen,