Graph isomorphism and theorems of Birkhoff type

Abstract

Two graphsG andG′ having adjacency matricesA andB are called ds-isomorphic iff there is a doubly stochastic matrixX satisfyingXA=BX.Ds-isomorphism is a relaxation of the classical isomorphism relation. In section 2 a complete set of invariants with respect tods-isomorphism is given. In the case whereA=B (ds-automorphism) the main question is: For which graphsG the polytope ofds-automorphisms ofG equals the convex hull of the automorphisms ofG? In section 3 a positive answer to this question is given for the cases whereG is a tree or whereG is a cycle. The corresponding theorems are analoga to the well known theorem of Birkhoff on doubly stochastic matrices.

Zusammenfassung

Zwei GraphenG undG′ werdends-isomorph genannt, wenn eine doppelt stochastische MatrixX existiert mitXA=BX, wobeiA undB die Adjazenzmatrizen vonG undG′ sind.Ds-Isomorphie ist eine Vergröberung der klassischen Isomorphierelation. In Abschnitt 2 wird ein vollständiges Invariantensystem bezüglichds-Isomorphie vorgestellt. Für den FallA=B (ds-Automorphismus) lautet die Hauptfrage: Für welche GraphenG ist das Polytop derds-Automorphismen gleich der konvexen Hülle der klassischen Automorphismen? In Abschnitt 3 wird diese Frage für Kreise und Bäume positiv beantwortet. Die entsprechenden Theoreme sind Analoga zu dem bekannten Satz von Birkhoff über doppelt stochastische Matrizen.