Complexity of Cocktail Party Graph and Crown Graph
- 1 Department of Mathematics, Faculty of Science, El-Minufiya University, Shebeen El-Kom, Egypt
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.
DOI: https://doi.org/10.3844/ajassp.2012.202.207
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.
- 3,812 Views
- 4,356 Downloads
- 5 Citations
Download
Keywords
- Complexity of graphs
- spanning trees
- cocktail party graphs
- chebyshev polynomials
- crown graph