The diameter of the acyclic Birkhoff polytope

摘要

In this work we give an interpretation of vertices and edges of the acyclic Birkhoff polytope, I-n = Omega(n) (T), where T is a tree with it vertices, in terms of graph theory. We generalize a recent result relatively to the diameter of the graph G(I-n). (c) 2007 Elsevier Inc. All rights reserved.