The d-dimensional rigidity matroid of sparse graphs
The d-dimensional rigidity matroid of sparse graphs
复制标题
稀疏图的d维刚性拟阵
DOI：
10.1016/j.jctb.2005.03.004
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Tibor Jordán
中科院分区：
文献类型：
--
作者：
Bill Jackson;Tibor Jordán
设Rd（G）是图G=（V，E）的d维刚性拟阵.设X ∈ V，i（X）为G中由X诱导的子图的边数.当G的最大度不超过d+2，最小度不超过d+1时，我们得到了确定Rd（G）中秩函数的一个极小极大公式.我们还证明了如果d是偶数且i（X）<$12 [（d+2）]| X|- （2d+2）]，对于所有X ∈ V，|X|则E在Rd（G）中是独立的。我们推测后一结果对所有d 2都成立，并在d=3的特殊情况下证明了这一点。我们使用的独立性结果，甚至d表明，如果G的连通性是足够大的相比，d，然后E有大的Rd（G）的秩。我们用d=4的情形证明，如果G是10-连通的，那么G在R3上是刚性的，只需钉住它的四分之三的顶点.
Let Rd(G) be the d-dimensional rigidity matroid for a graph G=(V,E). For X⊆V let i(X) be the number of edges in the subgraph of G induced by X. We derive a min-max formula which determines the rank function in Rd(G) when G has maximum degree at most d+2 and minimum degree at most d+1. We also show that if d is even and i(X)⩽12[(d+2)|X|-(2d+2)] for all X⊆V with |X|⩾2 then E is independent in Rd(G). We conjecture that the latter result holds for all d⩾2 and prove this for the special case when d=3. We use the independence result for even d to show that if the connectivity of G is sufficiently large in comparison to d then E has large rank in Rd(G). We use the case d=4 to show that, if G is 10-connected, then G can be made rigid in R3by pinning down approximately three quarters of its vertices.