Some Applications of Spanning Trees in Complete and Complete Bipartite Graphs

Abstract

Problem statement: The number of spanning trees τ(G) in graphs (networks) is an important invariant, it is also an important measure of reliability of a network. Approach: Using linear algebra and matrix analysis techniques to evaluate the associated determinants. Results: In this study we derive simple formulas for the number of spanning trees of complete graph K_n and complete bipartite graph K_n,m and some of their applications. A large number of theorems of number of the spanning trees of known operations on complete graph K_n and complete bipartite graph K_n,m are obtained. Conclusion: The evaluation of number of spanning trees is not only interesting from a mathematical (computational) perspective, but also, it is an important measure of reliability of a network and designing electrical circuits. Some computationally hard problems such as the travelling salesman problem can be solved approximately by using spanning trees. Due to the high dependence of the network design and reliability on the graph theory we introduced the following important theorems and lemmas and their proofs.