Journal of Mathematics and Statistics

Number of Spanning Trees of Circulant Graphs C6n and their Applications

S. N. Daoud

DOI : 10.3844/jmssp.2012.24.31

Journal of Mathematics and Statistics

Volume 8, Issue 1

Pages 24-31

Abstract

Problem statement: The number of spanning trees of a graph G is usually denoted by τ(G). A circulant graph with n vertices and k jumps is Cn (a1,…..,ak). Approach: In this study the number τ(G) of spanning trees of the circulant graphs C6n with some non-fixed jumps such as C6n (1, n), C6n (1, n, 2n), C6n (1, n, 3n), C6n (1, 2n 3n), C6n (1, n, 2n, 3n), are evaluated using Chebyshev polynomials. A large number of theorems of number of the spanning trees of circulate graphs C12n are obtained. Results: The number t(G) of spanning trees of the circulant graphs C6n(1, n), C6n(1, n, 2n), C6n(1, n, 3n), C6n(1, 2n, 3n), C6n(1, n, 2n, 3n), C12n(1, 2n, 3n), C12n(1, 3n, 6n), C12n(1, 3n, 4n), C12n(1, 2n, 3n, 4n), C12n(1, 2n, 3n, 6n), C12n(1, 3n, 4n, 6n) and C12n(1, 2n, 3n, 4n, 6n) are evaluated. 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 following important theorems and their proofs.