Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/13478
Title: The skeleton of acyclic Birkhoff polytopes
Author: Abreu, Nair
Costa, Liliana
Dahl, Geir
Martins, Enide
Keywords: Birkhoff polytope
Tree
Skeleton
Issue Date: Sep-2014
Publisher: Elsevier
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.
Peer review: yes
URI: http://hdl.handle.net/10773/13478
DOI: 10.1016/j.laa.2014.05.021
ISSN: 0024-3795
Appears in Collections:CIDMA - Artigos
DMat - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
The skeleton of acyclic Birkhoff.pdfDocumento Principal469.43 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.