Graph isomorphism and theorems of Birkhoff type (Q1068104)

From MaRDI portal
Revision as of 18:28, 10 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Graph isomorphism and theorems of Birkhoff type
scientific article

    Statements

    Graph isomorphism and theorems of Birkhoff type (English)
    0 references
    0 references
    1986
    0 references
    Two graphs G and G' having adjacency matrices A and B are called ds- isomorphic iff there is a doubly stochastic matrix X satisfying \(XA=BX\). Ds-isomorphism is a relaxation of the classical isomorphism relation. In section 2 a complete set of invariants with respect to ds-isomorphism is given. In the case where \(A=B\) (ds-automorphism) the main question is: For which graphs G the polytope of ds-automorphisms of G equals the convex hull of the automorhisms of G? In section 3 a positive answer to this question is given for the cases where G is a tree or where G is a cycle. The corresponding theorems are analoga to the well known theorem of Birkhoff on doubly stochastic matrices.
    0 references
    graph isomorphism
    0 references
    convex polytopes
    0 references
    doubly stochastic matrix
    0 references
    tree
    0 references
    cycle
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references