Thesis (1.3 MB)  Free access
Highlights
More informations
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 nonzero 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 ddimensional discrete tori to circulant graphs with first generator equals to 1 and to ddimensional degenerating discrete tori. They are degenerating in the sense that dp 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 dp sides. Furthermore, the results on ddimensional discrete tori enable to derive asymptotics for the number of spanning trees on ddimensional orthotope square lattices. Other results obtained in this thesis concern closed formulas for the number of spanning trees in directed and nondirected circulant graphs where the generators vary, that is, they linearly depend on the number of vertices.  
Identifiers  URN: urn:nbn:ch:unige818773  
Full text  
Structures  
Citation (ISO format)  LOUIS, Justine. Spanning trees in discrete tori, hypercubic lattices and circulant graphs. Université de Genève. Thèse, 2015. https://archiveouverte.unige.ch/unige:81877 