Counting degree sequences of spanning trees in bipartite graphs: A graph-theoretic proof |
| |
| Authors: | Anja Fischer Frank Fischer |
| |
| Affiliation: | 1. TU Dortmund University, Faculty of Business and Economics, Dortmund, Germany;2. Johannes Gutenberg University Mainz, Institute of Computer Science, Mainz, Germany |
| |
| Abstract: | Given a bipartite graph  with bipartition  each spanning tree in  has a degree sequence on  and one on  . Löhne and Rudloff showed that the number of possible degree sequences on  equals the number of possible degree sequences on  . Their proof uses a non-trivial characterization of degree sequences by  -draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result. |
| |
| Keywords: | bipartite graphs degree sequences spanning trees |
|
|
