Computing the degree of a vertex in the skeleton ofacyclic Birkhoff polytopes

For a fixed tree T with n vertices the corresponding acyclic Birkhoff polytope Ωn(T) consists of doubly stochastic matrices having support in positions specified by T (matrices associated with T). The skeleton of Ωn(T) is the graph whose vertices are the permutation matrices associated with T and two vertices (permutation matrices) A and B are adjacent if and only if (E(GA)\E(GB))\(E(GB)\E(GA)) is the edge set of a nontrivial path, where E(GA) and E(GB) are the edge sets of graphs associated with A and B, respectively. We present a formula to compute the degree of any vertex in the skeleton of Ωn(T). We also describe an algorithm for computing this number. In addition, we determine the maximum degree of a vertex in the skeleton of Ωn(T), for certain classes of trees, including paths and generalized stars where the branches have equal length. © 2015 Elsevier Inc.Allrightsreserved.