A note on certain subpolytopes of the assignment polytope associated with circulant graphs
A note on certain subpolytopes of the assignment polytope associated with circulant graphs
复制标题
关于与循环图相关的赋值多胞体的某些子多胞体的注释
DOI：
10.1016/0024-3795(88)90054-7
复制
发表时间：
1988
影响因子：
1.1
通讯作者：
G. Tinhofer
中科院分区：
文献类型：
--
作者：
H. Schreck;G. Tinhofer
对于n个素数顶点上的具有邻接矩阵A的非空非完全循环图G，考虑所有与A可交换的双随机矩阵X的多面体DS（G）。证明了DS（G）是整数当且仅当G的谱结构与n阶无向圈的谱结构相同。我们的定理的充分性部分被推广到任意复合顶点数的情况。
For a nonempty and noncomplete circulant graphGon a prime numbernof vertices with adjacency matrixA, consider the polytope DS(G) of all doubly stochastic matricesXwhich commute withA. It is shown that DS(G) is integral iff the spectral structure ofGis the same as for the undirected cycleonnvertices. The sufficiency part of our theorem is extended to the case of arbitrary composite vertex numbersn.