The blow-up conjecture for globally rigid graph constructions

Let GG be a connected graph with v>1v>1 vertices, denoted v1,,vvv_1,\ldots,v_v. Replacing each vertex viv_i by an independent set of size aia_i and connecting the new independent sets according to the edges of GG gives a graph constructed from GG by independent-set blow-ups.

Blow-up conjecture. For any connected graph GG with v>1v > 1, there exists some a1,a2,,ava_1, a_2, \ldots, a_v and some dd such that if we replace each viv_i with an independent set of size aia_i and connect them accordingly, the resulting graph is GPR in Rd\mathbb{R}^d.

This conjecture proposes a globally rigid construction for every connected graph with more than one vertex, extending the paper's experimentally observed and proved examples for irreducible graphs of small order, kk-chains, and kk-rings. The general assertion remains open in the supplied text.

Sources & referencesView supporting material

Primary source

Samuel Frank and Jiayang Jiang, “New Classes of Counterexamples to Hendrickson's Global Rigidity Conjecture”, arXiv:0909.2893 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.