## Sponsor

Portland State University. Department of Mathematics and Statistics

## 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

## Recommended Citation

Kummel, Ewan Joaquin, "Forest Generating Functions of Directed Graphs" (2023). *Dissertations and Theses.* Paper 6561.

https://doi.org/10.15760/etd.3693