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

For a fixed tree T with n   vertices the corresponding acyclic Birkhoff polytope Ωn(T)Ωn(T) consists of doubly stochastic matrices having support in positions specified by T (matrices associated with T  ). The skeleton of Ωn(T)Ω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))(E(GA)∖E(GB))∪(E(GB)∖E(GA)) is the edge set of a nontrivial path, where E(GA)E(GA) and E(GB)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)Ω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)Ωn(T), for certain classes of trees, including paths and generalized stars where the branches have equal length.