Orthogonal representations and connectivity of graphs (Q1823259)

An orthogonal representation of a graph G is an assignment of the vertices in G to vectors in \({\mathbb{R}}^ d\) such that non adjacent vertices are represented by orthogonal vectors. An orthogonal representation of G with the further property that any d representing vectors are linearly independent is called a general-position orthogonal representation of G (or GPOR of G). The paper shows that an n vertex graph G has a GPOR in \({\mathbb{R}}^ d\) if and only if G is (n-d) connected. An algorithm is given for finding the GPOR. The closure of the set of all \(GPOR^ s\) of a given graph is shown to be an irreducible algebraic variety.