The skeleton of acyclic Birkhoff polytopes

For a fixed tree T with n vertices the corresponding acyclic Birkhoff polytope Omega(n)(T) consists of doubly stochastic matrices having support in positions specified by T. This is a face of the Birkhoff polytope Omega(n) (which consists of all n x n doubly stochastic matrices). The skeleton of Omega(n)(T) is the graph where vertices and edges correspond to those of Omega(n)(T), and we investigate some properties of this graph. In particular, we characterize adjacency of pairs of vertices, compute the minimum degree of a vertex and show some properties of the maximum degree of a vertex in the skeleton. We also determine the maximum degree for certain classes of trees, including paths, stars and caterpillars. (C) 2014 Elsevier Inc. All rights reserved.