Automated Counting of Spanning Trees for Several Infinite Families of Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915858115198976 |
|---|---|
| author | Blanco, Pablo Zeilberger, Doron |
| author_facet | Blanco, Pablo Zeilberger, Doron |
| contents | Using the theoretical basis developed by Yao and Zeilberger, we consider certain graph families whose structure results in a rational generating function for sequences related to spanning tree enumeration. Said families are Powers of Cycles and Powers of Path; later, we briefly discuss Torus graphs and Grid graphs. In each case we know, a priori, that the set of spanning trees of the family of graphs can be described in terms of a finite-state-machine, and hence there is a finite transfer-matrix that guarantees the generating function is rational. Finding this ``grammar'', and hence the transfer-matrix is very tedious, so a much more efficient approach is to use experimental mathematics. Since computing numerical determinants is so fast, one can use the matrix tree theorem to generate sufficiently many terms, then fit the data to a rational function. The whole procedure can be done rigorously a posteriori. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Automated Counting of Spanning Trees for Several Infinite Families of Graphs Blanco, Pablo Zeilberger, Doron Combinatorics 05C30 05C30 05C30 Using the theoretical basis developed by Yao and Zeilberger, we consider certain graph families whose structure results in a rational generating function for sequences related to spanning tree enumeration. Said families are Powers of Cycles and Powers of Path; later, we briefly discuss Torus graphs and Grid graphs. In each case we know, a priori, that the set of spanning trees of the family of graphs can be described in terms of a finite-state-machine, and hence there is a finite transfer-matrix that guarantees the generating function is rational. Finding this ``grammar'', and hence the transfer-matrix is very tedious, so a much more efficient approach is to use experimental mathematics. Since computing numerical determinants is so fast, one can use the matrix tree theorem to generate sufficiently many terms, then fit the data to a rational function. The whole procedure can be done rigorously a posteriori. |
| title | Automated Counting of Spanning Trees for Several Infinite Families of Graphs |
| topic | Combinatorics 05C30 05C30 05C30 |
| url | https://arxiv.org/abs/2507.03841 |