Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Entire DC Network
Counting Spanning Trees On Triangular Lattices, Angie Wang
Counting Spanning Trees On Triangular Lattices, Angie Wang
CMC Senior Theses
This thesis focuses on finding spanning tree counts for triangular lattices and other planar graphs comprised of triangular faces. This topic has applications in redistricting: many proposed algorithmic methods for detecting gerrymandering involve spanning trees, and graphs representing states/regions are often triangulated. First, we present and prove Kirchhoff’s Matrix Tree Theorem, a well known formula for computing the number of spanning trees of a multigraph. Then, we use combinatorial methods to find spanning tree counts for chains of triangles and 3 × n triangular lattices (some limiting formulas exist, but they rely on higher level mathematics). For a chain of …