Research Article Open Access

Number of Spanning Trees of Circulant Graphs C6n and their Applications

S. N. Daoud

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.

Journal of Mathematics and Statistics
Volume 8 No. 1, 2012, 24-31

DOI: https://doi.org/10.3844/jmssp.2012.24.31

Submitted On: 1 November 2011 Published On: 12 December 2011

How to Cite: Daoud, S. N. (2012). Number of Spanning Trees of Circulant Graphs C6n and their Applications. Journal of Mathematics and Statistics, 8(1), 24-31. https://doi.org/10.3844/jmssp.2012.24.31

  • 3,367 Views
  • 2,038 Downloads
  • 3 Citations

Download

Keywords

  • Spanning trees
  • circulant graphs
  • chebyshev polynomials
  • kirchhoff matrix