一类完全二部图删边子图中包含给定森林的生成树计数
Counting Spanning Trees Containinga Given Forest in Edge-DeletedSubgraphs of a Class of CompleteBipartite Graphs
摘要: 本文主要构造了完全二部图删去星图边集后的电学等价图，并且利用 Teufl-Wagner 公式的推广形式，计算了其包含给定生成森林所有边的生成树数目。
Abstract: In this paper, we construct the electrical equivalent graph of the complete bipartite
graph after deleting the edge set of a star, and by applying a generalized form of the
Teufl-Wagner formula, we count the number of spanning trees that contain all edges
of a given spanning forest.
参考文献
|
[1]
|
Moon, J.W. (1964) The Second Moment of the Complexity of a Graph. Mathematika, 11,
95-98. [Google Scholar] [CrossRef]
|
|
[2]
|
Dong, F. and Ge, J. (2022) Counting Spanning Trees in a Complete Bipartite Graph Which
Contain a Given Spanning Forest. Journal of Graph Theory, 101, 79-94.[CrossRef]
|
|
[3]
|
Li, D., Chen, W. and Yan, W. (2023) Enumeration of Spanning Trees of Complete Multipartite
Graphs Containing a Fixed Spanning Forest. Journal of Graph Theory, 104, 160-170.[CrossRef]
|
|
[4]
|
Bollobas, B. (1998) Modern Graph Theory. Springer.
|
|
[5]
|
Teufl, E. and Wagner, S. (2010) Determinant Identities for Laplace Matrices. Linear Algebra
and Its Applications, 432, 441-457. [Google Scholar] [CrossRef]
|
|
[6]
|
Li, D. and Yan, W. (2025) A Variant of the Teufl‐Wagner Formula and Applications. Journal
of Graph Theory, 109, 68-75. [Google Scholar] [CrossRef]
|
|
[7]
|
Gervacio, S.V. (2016) Resistance Distance in Complete n-Partite Graphs. Discrete Applied
Mathematics, 203, 53-61. [Google Scholar] [CrossRef]
|
|
[8]
|
Chen, H. (2010) Random Walks and the Effective Resistance Sum Rules. Discrete Applied
Mathematics, 158, 1691-1700. [Google Scholar] [CrossRef]
|
|
[9]
|
Fiedler, M. and Sedláček, J. (1958) On w-Bases of Directed Graphs. Časopis pro pěstování
matematiky, 83, 214-225. [Google Scholar] [CrossRef]
|