Return to search

Methods from Linear Algebra for the Enumeration of Spanning Trees

In this report, we study the enumeration of spanning trees in graphs, using two methods withinlinear algebra, Kirchhoff’s Matrix Tree Theorem and an alternative method, also referred to asLemma 1, derived by S. Klee and M.T Stamps in [KS20]. Along with introducing preliminary tools from linear algebra, we also study the Laplace matrix ofa graph and use its properties in the two methods to derive combinatorical expressions on spanningtree enumeration of different graph families. We discuss properties of the Laplace matrix obtainedfrom different graph structures, and determine which method is more suitable in each case, withrespect to linear algebra. Specifically, complete graphs, Ferrers graphs and Windmill graphs areconsidered.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-331464
Date January 2023
CreatorsForsgren, Nils
PublisherKTH, Skolan för teknikvetenskap (SCI)
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess
RelationTRITA-SCI-GRU ; 2023:190

Page generated in 0.0016 seconds