UNIGE document Doctoral Thesis
previous document  unige:81877  next document
add to browser collection
Title

Spanning trees in discrete tori, hypercubic lattices and circulant graphs

Author
Director
Defense Thèse de doctorat : Univ. Genève, 2015 - Sc. 4867 - 2015/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.
Identifiers
URN: urn:nbn:ch:unige-818773
Full text
Thesis (1.3 MB) - public document Free access
Structures
Citation
(ISO format)
LOUIS, Justine. Spanning trees in discrete tori, hypercubic lattices and circulant graphs. Université de Genève. Thèse, 2015. https://archive-ouverte.unige.ch/unige:81877

363 hits

199 downloads

Update

Deposited on : 2016-03-14

Export document
Format :
Citation style :