Number of Spanning Trees of Circulant Graphs C_6n and their Applications

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 C_n (a₁,…..,a_k). Approach: In this study the number τ(G) of spanning trees of the circulant graphs C_6n with some non-fixed jumps such as C_6n (1, n), C_6n (1, n, 2n), C_6n (1, n, 3n), C_6n (1, 2n 3n), C_6n (1, n, 2n, 3n), are evaluated using Chebyshev polynomials. A large number of theorems of number of the spanning trees of circulate graphs C_12n are obtained. Results: The number t(G) of spanning trees of the circulant graphs C_6n(1, n), C_6n(1, n, 2n), C_6n(1, n, 3n), C_6n(1, 2n, 3n), C_6n(1, n, 2n, 3n), C_12n(1, 2n, 3n), C_12n(1, 3n, 6n), C_12n(1, 3n, 4n), C_12n(1, 2n, 3n, 4n), C_12n(1, 2n, 3n, 6n), C_12n(1, 3n, 4n, 6n) and C_12n(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.