Research Article Open Access

Some Applications of Spanning Trees in Complete and Complete Bipartite Graphs

S. N. Daoud1
  • 1 ,
American Journal of Applied Sciences
Volume 9 No. 4, 2012, 584-592

DOI: https://doi.org/10.3844/ajassp.2012.584.592

Submitted On: 27 November 2011 Published On: 15 February 2012

How to Cite: Daoud, S. N. (2012). Some Applications of Spanning Trees in Complete and Complete Bipartite Graphs. American Journal of Applied Sciences, 9(4), 584-592. https://doi.org/10.3844/ajassp.2012.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.

  • 1,152 Views
  • 2,831 Downloads
  • 5 Citations

Download

Keywords

  • Complete graph
  • complete bipartite graph
  • spanning trees
  • Kirchhoff matrix
  • operations on graphs