American Journal of Applied Sciences

Complexity of Cocktail Party Graph and Crown Graph

S. N. Daoud

DOI : 10.3844/ajassp.2012.202.207

American Journal of Applied Sciences

Volume 9, Issue 2

Pages 202-207


Problem statement: The number of spanning trees τ(G) in graphs (networks) was an important invariant. Approach: Using the properties of the Chebyshev polynomials of the second kind and the linear algebra techniques to evaluate the associated determinants. Results: The complexity, number of spanning trees, of the cocktail party graph on 2n vertices, given in detail in the text was proved. Also the complexity of the crown graph on 2n vertices was shown to had the value nn-2 (n-1) (n-2)n-1. Conclusion: The number of spanning trees τ(G) in graphs (networks) is an important invariant. The evaluation of this number and analyzing its behavior 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 above important theorems and lemmas and their proofs.


© 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.