Complexity of Cocktail Party Graph and Crown Graph

Abstract

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 n^n-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.