First Advisor

John Caughman

Term of Graduation

Fall 2023

Date of Publication

11-22-2023

Document Type

Dissertation

Degree Name

Doctor of Philosophy (Ph.D.) in Mathematical Sciences

Department

Mathematics and Statistics

Language

English

Subjects

Algebraic Graph Theory, Directed Graph, Externally Equitable Partition, Laplacian Matrix, Spanning Forest Polynomial

DOI

10.15760/etd.3693

Physical Description

1 online resource (vi, 124 pages)

Abstract

A spanning forest polynomial is a multivariate generating function whose variables are indexed over both the vertex and edge sets of a given directed graph. In this thesis, we establish a general framework to study spanning forest polynomials, associating them with a generalized Laplacian matrix and studying its properties. We introduce a novel proof of the famous matrix-tree theorem and show how this extends to a parametric generalization of the all-minors matrix-forest theorem. As an application, we derive explicit formulas for the recently introduced class of directed threshold graphs.

We prove that multivariate forest polynomials are, in general, irreducible and we define a number of specializations that may be compactly expressed in terms of various factors. A specialization in this context is an identification of some of the variables of the polynomial, for example evaluating f(x,y,z) as f(x,x,z). This allows us to derive results that generalize and extend many known properties of the traditional Laplacian matrix in algebraic graph theory.

We analyze the connection between the matrix algebra generated by the traditional Laplacian matrix and certain matrices of forest polynomials. Using this analysis, we derive explicit formulas for these matrices in the cases of Cartesian products of complete graphs and de Bruijn graphs. More generally, we derive an explicit formula relating spanning forest polynomials of a graph to the numbers of D-lazy walks in the graph. These are walks that may choose to remain at a given vertex if that vertex is not of maximum degree D.

This leads us to the study of externally equitable partitions (EEPs), which are objects of recent interest in the control theory literature. We prove that for graphs with EEPs satisfying an additional criteria, the specialized forest polynomials may be factored into a product of forest polynomials of related quotient graphs. We apply this theorem to complete multipartite graphs, hypercube graphs, directed line graphs, and others.

Rights

© 2023 Ewan Joaquin Kummel

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Persistent Identifier

https://archives.pdx.edu/ds/psu/41130

Download

Included in

Mathematics Commons

Share

COinS