en
Doctoral thesis
Open access
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.

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

Technical informations

Creation02/25/2016 6:15:00 PM
First validation02/25/2016 6:15:00 PM
Update time03/15/2023 12:12:58 AM
Status update03/15/2023 12:12:58 AM
Last indexation05/02/2024 5:20:55 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack