Orthogonal representations and connectivity of graphs
From MaRDI portal
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.
Recommendations
- On orthogonal representations of graphs
- A note on vector representation of graphs
- Orthogonal representations over finite fields and the chromatic number of graphs
- On the ideal of orthogonal representations of a graph in \(\mathbb{R}^2\)
- Topological bounds on the dimension of orthogonal representations of graphs
Cites work
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 4037787 (Why is no real title available?)
- scientific article; zbMATH DE number 3730165 (Why is no real title available?)
- On the Shannon capacity of a graph
- Relaxations of vertex packing
- Rubber bands, convex embeddings and graph connectivity
Cited in
(68)- Lower bounds in minimum rank problems
- Orthogonal structures in directed graphs
- Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
- A correction: Orthogonal representations and connectivity of graphs
- Lovász-Saks-Schrijver ideals and coordinate sections of determinantal varieties
- On orthogonal representations of graphs
- Graphs with magnetic Schrödinger operators of low corank
- The geometry of graphs and some of its algorithmic applications
- Generalized Greenberger-Horne-Zeilinger arguments from quantum logical analysis
- Subgraph complementation and minimum rank
- Book review of: L. Lovász, Graphs and geometry
- Faithful orthogonal representations of graphs from partition logics
- Positive matching decompositions of graphs
- Generically globally rigid graphs have generic universally rigid frameworks
- Vector representations of graphs and distinguishing quantum product states with one-way LOCC
- Orthonormal representations of \(H\)-free graphs
- Lovász-Saks-Schrijver ideals and parity binomial edge ideals of graphs
- Connectivity for quantum graphs
- Quantum violation of the suppes-zanotti inequalities and ``contextuality
- Representation of fragmentary structures by oriented graphs
- Topological bounds on the dimension of orthogonal representations of graphs
- Sharp lower and upper bounds for the Gaussian rank of a graph
- Orthogonal representations over finite fields and the chromatic number of graphs
- Regularity of powers of (parity) binomial edge ideals
- scientific article; zbMATH DE number 4026840 (Why is no real title available?)
- Classical, quantum and nonsignalling resources in bipartite games
- On the graph complement conjecture for minimum rank
- Graphs associated with vector spaces of even dimension: A link with differential geometry
- Tverberg’s theorem is 50 years old: A survey
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- Techniques for determining equality of the maximum nullity and the zero forcing number of a graph
- Regularity of parity binomial edge ideals
- Orthogonal embeddings of graphs in Euclidean space
- Approximating the orthogonality dimension of graphs and hypergraphs
- Roots and (re)sources of value (in)definiteness \textit{versus} contextuality
- The sheaf-theoretic structure of non-locality and contextuality
- Graph connectivity and universal rigidity of bar frameworks
- Bounds on minimum semidefinite rank of graphs
- Entanglement distillation from Greenberger-Horne-Zeilinger shares
- Optimal Transitions for Targeted Protein Quantification: Best Conditioned Submatrix Selection
- Approximating the orthogonality dimension of graphs and hypergraphs
- Noncontextual coloring of orthogonality hypergraphs
- Embedding graphs in Euclidean space
- Embedding graphs in Euclidean space
- Unextendible product bases
- The minimum rank problem for circulants
- Distinguishing orthogonality graphs
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- scientific article; zbMATH DE number 7692355 (Why is no real title available?)
- Hypergraph LSS-ideals and coordinate sections of symmetric tensors
- Sparks of symmetric matrices and their graphs
- Chordal graphs and distinguishability of quantum product states
- Kernelization for orthogonality dimension
- The weak version of the graph complement conjecture and partial results for the delta conjecture
- On positive matching decomposition conjectures of hypergraphs
- Normality, factoriality and strong F-regularity of Lovász-Saks-Schrijver rings
- Gröbner basis and Krull dimension of the Lovász-Saks-Sherijver ideal associated to a tree
- On the zero forcing number of trees
- (Almost) complete intersection Lovász-Saks-Schrijver ideals and the regularity of their powers
- Kernelization for orthogonality dimension
- New hardness results for low-rank matrix completion
- Kernelization for H-coloring
- On the ideal of orthogonal representations of a graph in \(\mathbb{R}^2\)
- Linearly independent vertices and minimum semidefinite rank
- Maximum generic nullity of a graph
- Three-connected graphs whose maximum nullity is at most three
- Orthogonal \(\sigma\)-labellings of graphs
- Expected values of parameters associated with the minimum rank of a graph
This page was built for publication: Orthogonal representations and connectivity of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823259)
