The polytope of degree partitions

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

The degree partition of a simple graph is its degree sequence rearranged in weakly decreasing order. The polytope of degree partitions (respectively, degree sequences) is the convex hull of all degree partitions (respectively, degree sequences) of a fixed length. We think of the degree sequence polytope as the symmetrization of the degree partition polytope and the degree partition polytope as the asymmetric part of the degree sequence polytope. The degree sequence polytope is a well studied object with formulas (generating functions) known for its face numbers, volume, and number of lattice points. We study the degree partition polytope and determine its extreme points, edges, and facets. In particular, the degree partition polytope on n vertices has 2^{n-1} extreme points.
21 pages

Keywords

Combinatorics, 05c07, 90c27, 90c57

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/106275

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0512402
 http://arxiv.org/abs/math/0512402

Collections

arXiv