Musings on matchings, matrices, and multiplicities

Abstract

The Parter-Wiener Theorem is a celebrated contribution to the inverse eigenvalue problem for trees due to its determination of vertices whose removal affects multiplicities of eigenvalues in a non-intuitive manner. For a more general graph, G, that contains cycles, the construction of the weighted matching polynomial and its many properties are derived. These properties are shown to determine a relationship between the multiplicities of the roots of the weighted matching polynomial and the graph operation of vertex deletion in G, which is the operation at the core of the Parter-Wiener Theorem. Solutions for locating vertices whose removal increases the multiplicity of a root are presented, which gives rise to a new classification of graphs, called SRSI graphs. These graphs, along with graphs that have Hamilton paths, are determined to have a trivial variation of the Parter-Wiener Theorem. In an effort to determine the location of Parter vertices, vertices are categorized into classes based on their effects of root multiplicities, and, in the case of zero roots, the location of Parter vertices are explicitly noted. Moreover, computational results regarding the process of categorizing vertices into these classes are outlined, and the Vandermonde eigenvector test is established with the assistance of companion matrices. A myriad of results throughout the thesis are then used to determine a partially-generalized Parter-Wiener Theorem for this weighted matching polynomial.