A zonotope associated with graphical degree sequences. (English) Zbl 0737.05057

Stanley, Richard P.

Applied geometry and discrete mathematics, Festschr. 65th Birthday Victor Klee, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 4, 555-570 (1991).

[For the entire collection see Zbl 0726.00015.]
Author’s abstract: “Let \(D_ n\) denote the convex hull in \(\mathbb{R}^ n\) of all (ordered) degree sequences of simple \(n\)-vertex graphs. Using the fact that \(D_ n\) is a zonotope, an explicit generating functions is found for the number of these degree sequences. The \(f\)-vector of \(D_ n\) is found using Zaslavsky’s theory of signed graph colorings. Finally we give a generalization based on a result of Fulkerson, Hoffman, and MacAndrew.”.

Reviewer: E.M.Palmer (East Lansing)

MSC:

05C30	Enumeration in graph theory
52Bxx	Polytopes and polyhedra

Keywords:

degree sequences; zonotope