Research Article Open Access

Complexity of Cocktail Party Graph and Crown Graph

S. N. Daoud1
  • 1 ,
American Journal of Applied Sciences
Volume 9 No. 2, 2012, 202-207

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

Submitted On: 31 October 2011 Published On: 12 December 2011

How to Cite: Daoud, S. N. (2012). Complexity of Cocktail Party Graph and Crown Graph. American Journal of Applied Sciences, 9(2), 202-207. https://doi.org/10.3844/ajassp.2012.202.207

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

  • 1,266 Views
  • 2,522 Downloads
  • 3 Citations

Download

Keywords

  • Complexity of graphs
  • spanning trees
  • cocktail party graphs
  • chebyshev polynomials
  • crown graph