Counting rooted spanning foresrs in cobordism of two circulant graphs

N. V. Abrosimov, G. A. Baigonakova, L. A. Grunwald, I. A. Mednykh

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a family of graphs H-n(s(1), ..., s(k); t(1), ...,t(l)), which is a generalization of the family of I-graphs, which in turn, includes the generalized Petersen graphs and the prism graphs. We present an explicit formula for the number f(H)(n) of rooted spanning forests in these graphs in terms of Chebyshev polynomials and find its asymptotics. Also, we show that the number of rooted spanning forests can be represented in the form f(H)(n) = p a(n)(2), where a(n) is an integer sequence and p is a prescribed integer depending on the number of odd elements in the sequence s(1), ..., s(k), t(1), ..., t(l) and the parity of n.
Original languageEnglish
Pages (from-to)814-823
Number of pages10
JournalSiberian Electronic Mathematical Reports
Volume17
DOIs
Publication statusPublished - 2020

Keywords

  • circulant graph
  • I-graph
  • Petersen graph
  • prism graph
  • spanning forest
  • Chebyshev polynomial
  • Mahler measure
  • TREE FORMULAS
  • I-GRAPHS
  • NUMBER
  • ENUMERATION
  • COMPLEXITY

OECD FOS+WOS

  • 1.01 MATHEMATICS

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

Cite this