Graduation Year
2016
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Mohamed Omar
Reader 2
Nicholas Pippenger
Terms of Use & License Information
This work is licensed under a Creative Commons Attribution-Noncommercial 3.0 License
Rights Information
© 2016 Cheng Wai Koo
Abstract
Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees.
Our other results are combinatorial proofs that the conjecture holds for graphs having |X| ≤ 2, for even cycles, and under the operation of connecting two graphs by a new edge.
We also make two new conjectures based on empirical data, each of which is stronger than Ehrenborg's conjecture.
Recommended Citation
Koo, Cheng Wai, "A Bound on the Number of Spanning Trees in Bipartite Graphs" (2016). HMC Senior Theses. 73.
https://scholarship.claremont.edu/hmc_theses/73
Source Fulltext
https://www.math.hmc.edu/~ckoo/thesis/ckoo-2016-thesis.pdf
