Orthogonal representations and connectivity of graphs
type: Item
instance of: scholarly article
title: Orthogonal representations and connectivity of graphs
zbMATH Open document ID: 0681.05048
DOI: 10.1016/0024-3795(89)90475-8
author: Michael Saks
author: László Lovász
author: Alexander Schrijver
published in: Linear Algebra and its Applications
publication date: 1989-01-01T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/10069
review text: 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.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 14A10
Mathematics Subject Classification ID: 15A03
zbMATH DE Number: 4114679
zbMATH Keywords: k-connected graphs
zbMATH Keywords: orthogonal representation of a graph
zbMATH Keywords: irreducible algebraic variety
reviewed by: R. E. L. Aldred
MaRDI profile type: Publication
OpenAlex ID: W2145167573
cites work: Q3918134
cites work: Q3216686
cites work: Relaxations of vertex packing
cites work: Rubber bands, convex embeddings and graph connectivity
cites work: On the Shannon capacity of a graph
cites work: Q3777964
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
description: scientific article; zbMATH DE number 4114679