Counting spanning trees in cobordism of two circulant graphs

Galya Amanboldynovna Baigonakova, Ilya Aleksandrovich Mednykh

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

We consider a family of graphs Hn(s1, ..., sk; t1, ..., tl) that is a generalisation of the family of I-graphs, which, in turn, includes the generalized Petersen graphs. We present an explicit formula for the number τ(n) of spanning trees in these graphs in terms of the Chebyshev polynomials and find its asymptotics. Also, we show that the number of spanning trees can be represented in the form τ(n) = p n a(n)2; where a(n) is an integer sequence and p is a prescribed integer depending on the number of even elements in the sequence s1, ..., sk; t1, ..., tl and the parity of n.

Original languageEnglish
Pages (from-to)1145-1157
Number of pages13
JournalСибирские электронные математические известия
Volume15
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Chebyshev polynomial
  • Circulant graph
  • I-graph
  • Mahler measure
  • Petersen graph
  • Spanning tree
  • I-GRAPHS
  • NUMBER
  • spanning tree
  • COMPLEXITY
  • circulant graph
  • FORMULAS

Fingerprint

Dive into the research topics of 'Counting spanning trees in cobordism of two circulant graphs'. Together they form a unique fingerprint.

Cite this