Counting degree sequences of spanning trees in bipartite graphs: A graph-theoretic proof

被引：0

作者：

Fischer, Anja ^{[1
]}

Fischer, Frank ^{[2
]}

机构：

[1] TU Dortmund Univ, Fac Business & Econ, Vogelpothsweg 87, D-44227 Dortmund, Germany

[2] Johannes Gutenberg Univ Mainz, Inst Comp Sci, Mainz, Germany

来源：

JOURNAL OF GRAPH THEORY | 2019年 / 92卷 / 03期

关键词：

bipartite graphs; degree sequences; spanning trees;

D O I：

10.1002/jgt.22449

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given a bipartite graph G = (S (boolean OR) over dot T, E) with bipartition S, T each spanning tree in G has a degree sequence on S and one on T. Lohne and Rudloff showed that the number of possible degree sequences on S equals the number of possible degree sequences on T. Their proof uses a non-trivial characterization of degree sequences by G-draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result.

引用

页码：230 / 236

页数：7

共 4 条

[1]

KABANOV Y., 1999, Finance Stoch., V3, P237, DOI DOI 10.1007/S007800050061

[2] On the dual of the solvency cone [J].

Loehne, Andreas ;

Rudloff, Birgit .

DISCRETE APPLIED MATHEMATICS, 2015, 186 :176-185

[3] Permutohedra, Associahedra, and Beyond [J].

Postnikov, Alexander .

INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2009, 2009 (06) :1026-1106

[4] The fundamental theorem of asset pricing under proportional transaction costs in finite discrete time [J].

Schachermayer, W .

MATHEMATICAL FINANCE, 2004, 14 (01) :19-48

← 1 →