On reorienting graphs by pushing down maximal vertices—II

We provide a new proof of Propp's Theorem that the set of orientations of a graph G with a given flow difference can be made into a distributive lattice by allowing all vertices except a distinguished sink vertex to be pushed down. The method used allows us to determine the irreducible elements...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2003-08, Vol.270 (1), p.227-240
Main Author: Pretzel, Oliver
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Flow difference
Graph
Graph theory
Lattice
Mathematics
Orientation
Pushing down
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We provide a new proof of Propp's Theorem that the set of orientations of a graph G with a given flow difference can be made into a distributive lattice by allowing all vertices except a distinguished sink vertex to be pushed down. The method used allows us to determine the irreducible elements of this lattice and describe how the lattice changes if the sink varies.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(03)00160-2