Graph isomorphism and theorems of Birkhoff type (Q1068104)

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.