A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a *doubly-stochastic automorphism* of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph is clearly a doubly-stochastic automorphism.


A graph all of whose doubly-stochastic automorphisms are convex combinations of (classical) automorphisms is called *compact*. (E.g., trees and cycles are known to be compact, complement of compact graphs are compact as long as they are connected, while Petersen's graph to be *non*-compact)


If a graph is not compact, how do the further extremal points of the polytope of its doubly-stochastic automorphisms look like? Are there any known examples?



doubly-stochastic isomorphisms of graphs
A way to compute some extremal points for the Petersen example might be as follows: take the complement $A$ of its adjacency matrix and form the linear function $\ell(X)$ given by $X\mapsto \langle A,X\rangle$ on the space of 10x10 matrices. Maximising $\ell$ on the polytope in question using a simplex method will give you a vertex $Y$, such that $\ell(Y)\geq\ell(\frac{1}{6}A)=5$; you will get the equality in the latter, i.e. $\frac{1}{6}A$ is extremal (see the next paragraph for a proof). Note that [Evdokimov et al.](http://dx.doi.org/10.1016/S0012-365X%2899%2990071-7) showed that $\frac{1}{6}A$ is a point in the polytope which is not a convex combination of classical automorphisms, although they did not seem to care about extremality.


As well, there is the following more theoretical way to produce extreme points, although not vertices in general: observe that the polytope is invariant under the automorphism group $G\cong S\_5$ of the graph, and preserves the function $\ell$. Thus the image $g(Y)$ of $Y$ under any automorphism $g\in G$ satisfies $\ell(Y)=\ell(g(Y))$, and $Z:=\frac{1}{|G|}\sum\_{g\in G} g(Y)$ is also in the polytope and satisfies $\ell(Z)=\ell(Y)$, i.e. is extremal. On the other hand, $Z=\alpha I +\beta A +\gamma (ee^\top -I-A)$, for some nonnegative $\alpha$, $\beta$, $\gamma$, such that $Z$ is doubly stochastic, i.e. $\alpha+\frac{1}{6}\beta+\frac{1}{3}\gamma=1$. Therefore the set of such matrices $Z$ is the intersection of our polytope with certain 2-dimensional affine subspace. On this 2-dimensional polytope the linear function $\ell$ reaches the maximum at $Z=\frac{1}{6}A$. Therefore $\frac{1}{6}A$ is extremal in the whole polytope.


Finally, note that the latter argument generalises to the other graphs (Johnson graphs $J(n,k)$) in [loc.cit](http://dx.doi.org/10.1016/S0012-365X%2899%2990071-7), Thm 5.3.


EDIT: note that the Petersen graph (with the adjacency matrix $B:=ee^\top -I-A$) is not compact itself, as its complement (with the adjacency matrix $A$) is not compact. To see this, note that $XA=AX$ if and only if $XB=BX$, i.e. it does not matter which matrix equation we use to define our polytope. ([loc.cit.](http://dx.doi.org/10.1016/S0012-365X%2899%2990071-7) merely says that $A$ generates the corresponding matrix algebra, and the meaning of this remark might be lost on a casual reader).


