Doctoral thesis
OA Policy
English

Spanning trees in discrete tori, hypercubic lattices and circulant graphs

ContributorsLouis, Justine
Defense date2015-12-01
Abstract

In this thesis we study the number of spanning trees in some classes of graphs. This is made possible by the famous matrix tree theorem established by Kirchhoff in 1847 which states that the number of spanning trees in a finite graph is given by the product of the non-zero eigenvalues of the combinatorial Laplacian of the graph divided by the number of vertices. We adapt techniques derived by Chinta, Jorgenson and Karlsson in 2010 for d-dimensional discrete tori to circulant graphs with first generator equals to 1 and to d-dimensional degenerating discrete tori. They are degenerating in the sense that d-p sides of the tori are tending to infinity at the same rate while the p other sides tend to infinity sublinearly with respect to the d-p sides. Furthermore, the results on d-dimensional discrete tori enable to derive asymptotics for the number of spanning trees on d-dimensional orthotope square lattices. Other results obtained in this thesis concern closed formulas for the number of spanning trees in directed and non-directed circulant graphs where the generators vary, that is, they linearly depend on the number of vertices.

Citation (ISO format)
LOUIS, Justine. Spanning trees in discrete tori, hypercubic lattices and circulant graphs. Doctoral Thesis, 2015. doi: 10.13097/archive-ouverte/unige:81877
Main files (1)
Thesis
accessLevelPublic
Identifiers
946views
505downloads

Technical informations

Creation25/02/2016 18:15:00
First validation25/02/2016 18:15:00
Update time15/03/2023 00:12:58
Status update15/03/2023 00:12:58
Last indexation31/10/2024 02:59:55
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack