A necessary condition for generic rigidity of bar‐and‐joint frameworks in d‐space. Issue 2 (8th September 2021)

• Record Type: Journal Article
• Authors: Guler, Hakan; Jackson, Bill
• Is Part Of: Journal of graph theory. Volume 99:Issue 2(2022)
• Page Start: 231
• Page End: 239
• Publication Date: 2021-09-08
• Subjects: bar–joint framework -- infinitesimal rigidity -- rigidity matroid; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22737
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A graph G = ( V, E ) is d ‐sparse if each subset X ⊆ V with ∣ X ∣ ≥ d induces at most d ∣ X ∣ − d + 1 2 edges in G . Maxwell showed in 1864 that a necessary condition for a generic bar‐and‐joint framework with at least d + 1 vertices to be rigid in R d is that G should have a d ‐sparse subgraph with d ∣ X ∣ − d + 1 2 edges. This necessary condition is also sufficient when d = 1, 2 but not when d ≥ 3 . Cheng and Sitharam strengthened Maxwell's condition by showing that every maximal d ‐sparse subgraph of G should have d ∣ X ∣ − d + 1 2 edges when d = 3 . We extend their result to all d ≤ 11 .