Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647900 | Discrete Mathematics | 2012 | 7 Pages |
Abstract
Boesch’s theorem says that “Suppose that a connected graph GG has two non-adjacent 2-degree vertices u1u1 and u2u2. Then t(G)≤t(G/{u1,u2})t(G)≤t(G/{u1,u2}), where t(G)t(G) is the number of spanning trees of GG.” In this paper, we generalize this theorem as follows: “Suppose that GG is a connected graph of order at least 3, and that u1u1 and u2u2 are two vertices of degree mm and nn, respectively, in GG. Then t(G)≤mn−m02m+n−2m0t(G/{u1,u2}), where m0(≥0) is the number of multiple edges between u1u1 and u2u2.”
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Maolin Hu, Yongxi Cheng, Weidong Xu,