Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4599396 | Linear Algebra and its Applications | 2014 | 20 Pages |
Abstract
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. This is a face of the Birkhoff polytope Ωn (which consists of all nÃn doubly stochastic matrices). The skeleton of Ωn(T) is the graph where vertices and edges correspond to those of Ω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.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Nair Abreu, Liliana Costa, Geir Dahl, Enide Martins,