Orthogonal representations and connectivity of graphs (Q1823259): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 3 users not shown)
Property / author
 
Property / author: Michael E. Saks / rank
 
Normal rank
Property / author
 
Property / author: Alexander Schrijver / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: R. E. L. Aldred / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2145167573 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3918134 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3216686 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relaxations of vertex packing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Rubber bands, convex embeddings and graph connectivity / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Shannon capacity of a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3777964 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities / rank
 
Normal rank

Latest revision as of 09:37, 20 June 2024

scientific article
Language Label Description Also known as
English
Orthogonal representations and connectivity of graphs
scientific article

    Statements

    Orthogonal representations and connectivity of graphs (English)
    0 references
    0 references
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    k-connected graphs
    0 references
    orthogonal representation of a graph
    0 references
    irreducible algebraic variety
    0 references

    Identifiers