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
相关论文
共 17 条
  • [1] Degree Conditions for Completely Independent Spanning Trees of Bipartite Graphs
    Yuan, Jun
    Zhang, Ru
    Liu, Aixia
    GRAPHS AND COMBINATORICS, 2022, 38 (06)
  • [2] Degree Conditions for Completely Independent Spanning Trees of Bipartite Graphs
    Jun Yuan
    Ru Zhang
    Aixia Liu
    Graphs and Combinatorics, 2022, 38
  • [3] Spanning trees in graphs without large bipartite holes
    Han, Jie
    Hu, Jie
    Ping, Lidan
    Wang, Guanghui
    Wang, Yi
    Yang, Donglei
    COMBINATORICS PROBABILITY AND COMPUTING, 2024, 33 (03) : 270 - 285
  • [4] Counting spanning trees on fractal graphs and their asymptotic complexity
    Anema, Jason A.
    Tsougkas, Konstantinos
    JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, 2016, 49 (35)
  • [5] Counting spanning trees of (1, N)-periodic graphs
    Zhang, Jingyuan
    Lu, Fuliang
    Jin, Xian'an
    DISCRETE APPLIED MATHEMATICS, 2024, 344 : 88 - 101
  • [6] Full degree spanning trees in random regular graphs
    Acquaviva, Sarah
    Bal, Deepak
    DISCRETE APPLIED MATHEMATICS, 2024, 353 : 85 - 93
  • [7] Degree-preserving spanning trees in small-degree graphs
    Damaschke, P
    DISCRETE MATHEMATICS, 2000, 222 (1-3) : 51 - 60
  • [8] COUNTING SPANNING TREES IN PRISM AND ANTI-PRISM GRAPHS
    Sun, Weigang
    Wang, Shuai
    Zhang, Jingyuan
    JOURNAL OF APPLIED ANALYSIS AND COMPUTATION, 2016, 6 (01): : 65 - 75
  • [9] Universality for bounded degree spanning trees in randomly perturbed graphs
    Boettcher, Julia
    Han, Jie
    Kohayakawa, Yoshiharu
    Montgomery, Richard
    Parczyk, Olaf
    Person, Yury
    RANDOM STRUCTURES & ALGORITHMS, 2019, 55 (04) : 854 - 864
  • [10] The number and degree distribution of spanning trees in the Tower of Hanoi graph
    Zhang, Zhongzhi
    Wu, Shunqi
    Li, Mingyun
    Comellas, Francesc
    THEORETICAL COMPUTER SCIENCE, 2016, 609 : 443 - 455
12