Convex polyhedra of doubly stochastic matrices: II. Graph of Ωn

Properties of the graph $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ of the polytope $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices are studied. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is not a k-dimensional rectangular parallelotope for k ≥ 2, then G($\text{F}$) is Hamilton connected. Prime factor decompositions of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ relative to Cartesian product are investigated. In particular, if $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then the number of prime graphs in any prime factor decomposition of G($\text{F}$) equals the number of connected components of the neighborhood of any vertex of G($\text{F}$). Distance properties of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ are obtained. Faces $\text{F}$ of $\text{Ω}{}_{\mathrm{n}}$ for which G($\text{F}$) is a clique of $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ are investigated.