A New Interpretation of the Matrix Tree Theorem Using Weak Walk Contributions and Circle Activation
Date
2015-12
Authors
Robinson, Ellen Beth
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis provides an alternate proof of the Matrix Tree Theorem by shifting the focus to oriented incidences. We examine the weak walk contributors from the de-terminant of the Laplacian matrix of oriented graphs and classify them according to similar circle structures attained through circle activation. The members of each of these contribution classes form an alternating rank-signed Boolean lattice in which all members cancel. We then restrict our contributors to those corresponding to a given cofactor Lij and demonstrate that those contributors that no longer cancel are in one-to-one correspondence with the spanning trees of the graph. These results allow for possible extension into examining tree-counts in signed graphs and oriented hypergraphs.
Description
Keywords
graphs, matrix, trees, combinatorics, graph Theory, signed graphs, Honors College
Citation
Robinson, E. B. (2015). A new interpretation of the Matrix Tree Theorem using weak walk contributions and circle activation (Unpublished thesis). Texas State University, San Marcos, Texas.