A note on certain subpolytopes of the assignment polytope associated with circulant graphs

AbstractFor a nonempty and noncomplete circulant graph G on a prime number n of vertices with adjacency matrix A, consider the polytope DS(G) of all doubly stochastic matrices X which commute with A. It is shown that DS(G) is integral iff the spectral structure of G is the same as for the undirected cycleon n vertices. The sufficiency part of our theorem is extended to the case of arbitrary composite vertex numbers n