Weighted spanning trees on some self-similar graphs

MaRDI QIDQ625378zbMATH OpenFDO

Authors Daniele D'Angeli, Alfredo Donno

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.0021, https://eudml.org/doc/233775, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p16.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Signed and weighted graphs (05C22) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Groups acting on trees (20E08)

Abstract: We compute the complexity of two infinite families of finite graphs: the Sierpi'{n}ski graphs, which are finite approximations of the well-known Sierpi'nsky gasket, and the Schreier graphs of the Hanoi Towers group $H^{(3)}$ acting on the rooted ternary tree. For both of them, we study the weighted generating functions of the spanning trees, associated with several natural labellings of the edge sets.

Review text

Summary: We compute the complexity of two infinite families of finite graphs: the Sierpiński graphs, which are finite approximations of the well-known Sierpiński gasket, and the Schreier graphs of the Hanoi Towers group \(H^{(3)}\) acting on the rooted ternary tree. For both of them, we study the weighted generating functions of the spanning trees, associated with several natural labellings of the edge sets.

Recommendations

• Spanning trees of finite Sierpiński graphs
• The number of spanning trees in self-similar graphs
• The Tutte polynomial of the Sierpiński and Hanoi graphs
• Counting dimer coverings on self-similar Schreier graphs
• Spanning trees on the Sierpinski gasket

Cited in

(13)

• Enumeration of spanning trees in the sequence of Dürer graphs
• Complexity of the circulant foliation over a graph
• On Jacobian group and complexity of the generalized Petersen graph \(\mathrm{GP}(n,k)\) through Chebyshev polynomials
• The Tutte polynomial of the Sierpiński and Hanoi graphs
• Enumeration of spanning trees on Apollonian networks
• Tutte polynomial of the Apollonian network
• Schreier spectrum of the Hanoi Towers group on three pegs
• Spanning trees of finite Sierpiński graphs
• The critical group of a clique-inserted graph
• Counting dimer coverings on self-similar Schreier graphs
• Counting spanning trees in prism and anti-prism graphs
• A survey and classification of Sierpiński-type graphs
• On Jacobian group and complexity of the -graph

This page was built for publication: Weighted spanning trees on some self-similar graphs

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