American Journal of Applied Sciences

Some Applications of Spanning Trees in Complete and Complete Bipartite Graphs

S. N. Daoud

DOI : 10.3844/ajassp.2012.584.592

American Journal of Applied Sciences

Volume 9, Issue 4

Pages 584-592

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 Kn and complete bipartite graph Kn,m and some of their applications. A large number of theorems of number of the spanning trees of known operations on complete graph Kn and complete bipartite graph Kn,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.

Copyright

© 2012 S. N. Daoud. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.