Complexity of the circulant foliation over a graph

Research output: Contribution to journalArticlepeer-review

Abstract

In the present paper, we investigate the complexity of infinite family of graphs Hn=Hn(G1,G2,…,Gm) obtained as a circulant foliation over a graph H on m vertices with fibers G1,G2,…,Gm. Each fiber Gi=Cn(si,1,si,2,…,si,ki) of this foliation is the circulant graph on n vertices with jumps si,1,si,2,…,si,ki. This family includes the family of generalized Petersen graphs, I-graphs, sandwiches of circulant graphs, discrete torus graphs and others. We obtain a closed formula for the number τ(n) of spanning trees in Hn in terms of Chebyshev polynomials, investigate some arithmetical properties of this function and find its asymptotics as n→ ∞.

Original languageEnglish
Pages (from-to)115-129
Number of pages15
JournalJournal of Algebraic Combinatorics
Volume53
Issue number1
DOIs
Publication statusPublished - Feb 2021

Keywords

  • Chebyshev polynomials
  • Circulant graphs
  • I-graphs
  • Laplacian matrices
  • Petersen graphs
  • Spanning trees
  • NUMBER
  • JACOBIAN GROUP
  • COUNTING SPANNING-TREES
  • FORMULAS

Fingerprint Dive into the research topics of 'Complexity of the circulant foliation over a graph'. Together they form a unique fingerprint.

Cite this