A formula for the number of spanning trees in circulant graphs with nonfixed generators and discrete tori

DOI10.1017/S0004972715000969MaRDI QIDQ3458375zbMATH OpenOpenAlexFDO

Authors Justine Louis

Publication date 18 December 2015

Published in Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.4389

zbMATH Keywords

circulant graphsspanning tree entropyspanning trees

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

Abstract: We consider the number of spanning trees in circulant graphs of $$ vertices with generators depending linearly on $n$. The matrix tree theorem gives a closed formula of $$ factors, while we derive a formula of $$ factors. Using the same trick, we also derive a formula for the number of spanning trees in discrete tori. Moreover, the spanning tree entropy of circulant graphs with fixed and non-fixed generators is compared.

Recommendations

• The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic
• The numbers of spanning trees in undirected circulant graphs
• The numbers of spanning trees of some families of circulant graphs
• The number of spanning trees in circulant graphs
• Spanning trees in directed circulant graphs and cycle power graphs

Cites work

• Asymptotic Enumeration of Spanning Trees
• Chebyshev polynomials and spanning tree formulas for circulant and related graphs
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• Spanning tree formulas and Chebyshev polynomials
• The asymptotic number of spanning trees in circulant graphs

Cited in

(16)

• An explicit prime geodesic theorem for discrete tori and the hypergeometric functions
• Complexity of the circulant foliation over a graph
• Asymptotic analysis of determinant of discrete Laplacian
• Complexity of discrete Seifert foliations over a graph
• Asymptotics for the determinant of the combinatorial Laplacian on hypercubic lattices
• Number of spanning trees in the sequence of some nonahedral graphs
• Spanning trees in directed circulant graphs and cycle power graphs
• Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics
• The spanning trees formulas in a class of double fixed-step loop networks (extended abstract)
• On Rationality of Generating Function for the Number of Spanning Trees in Circulant Graphs
• Counting spanning trees of (1, N)-periodic graphs
• Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians
• On the complexity of Cayley graphs on a dihedral group
• The structure of the characteristic polynomial of the Laplacian matrix for a circulant graph with non-fixed jumps
• Counting the number of spanning trees in a class of double fixed-step loop networks
• Asymptotics for the number of spanning trees in circulant graphs and degenerating \(d\)-dimensional discrete tori

This page was built for publication: A formula for the number of spanning trees in circulant graphs with nonfixed generators and discrete tori

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3458375)