Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949583 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
Based on electrically equivalent transformations on weighted graphs, in this paper, we present a formula for computing the number of spanning trees of a family of 2-separable graphs formed from two base graphs by 2-sum operations. As applications, we compute the number of spanning trees of some special 2-separable graphs. Then comparisons are made between the number of spanning trees and the number of acyclic orientations for this family of 2-separable graphs under certain constraints. We also show that a factorization formula exists for the sum of weights of spanning trees of a special splitting graph.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Helin Gong, Shuli Li,