The blow-up conjecture for globally rigid graph constructions
The blow-up conjecture for globally rigid graph constructions
Let be a connected graph with vertices, denoted . Replacing each vertex by an independent set of size and connecting the new independent sets according to the edges of gives a graph constructed from by independent-set blow-ups.
Blow-up conjecture. For any connected graph with , there exists some and some such that if we replace each with an independent set of size and connect them accordingly, the resulting graph is GPR in .
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, -chains, and -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.