Mathfest and Summer Research 2019
Mathfest, August 2019
The Linear and Cyclic Bandwidth of a Graph
Zachary Lippe and Amy Kucera
The graph bandwidth problem can be thought of as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called a linear embedding of the graph and the minimum of all possible embeddings is called the bandwidth of the graph. An extension of this problem is to identify the vertices of a graph with the vertices of the cycle graph so that the length of the longest edge is minimized. Such a realization of the graph is called a cyclic embedding of the graph and the minimum of all possible cyclic embeddings is called the cyclic bandwidth of the graph. In this talk, we explore properties of linear and cyclic embeddings of certain graphs and their respective bandwidths.
Mathfest
Xavier Symposium
3-Cutwidth of Product Graphs
Beth Root
The graph cyclic bandwidth problem can be thought of as identifying the vertices of a graph with the vertices of the cycle graph so that the length of the longest edge is minimized. Such a realization of the graph is called a cyclic embedding of the graph and the minimum of all possible cyclic embeddings is called the cyclic bandwidth of the graph. We say a graph G is k-cyclic bandwidth, if its cyclic bandwidth is k. Furthermore, if any proper subgraph of G has a smaller cyclic bandwidth, we say that G is k-cyclic-bandwidth-critical. In this talk, we explore classes of graphs that are 3-cyclic-bandwidth, and identify the 3-cyclic-bandwidth-critical graphs.
3-Cyclic Bandwidth and 3-Cyclic Bandwidth Critical Graphs
Amanda Cusimano
The graph cyclic bandwidth problem can be thought of as identifying the vertices of a graph with the vertices of the cycle graph so that the length of the longest edge is minimized. Such a realization of the graph is called a cyclic embedding of the graph and the minimum of all possible cyclic embeddings is called the cyclic bandwidth of the graph. We say a graph G is a k-cyclic bandwidth, if its cyclic bandwidth is k. Furthermore, if any proper subgraph of G has a smaller cyclic bandwidth, we say that G is k-cyclic-bandwidth-critical. In this talk, we explore classes of graphs that are 3-cyclic-bandwidth, and identify the 3-cyclic-bandwidth-critical graphs.
An Exploration of Various Matrices Associated with a Given Graph
Emma Hiatt
Given a graph we associate a matrix by assigning to each pair of vertices a value that would correspond to an entry in the matrix. The most well-known example of a matrix associated with a graph is the adjacency matrix, but other matrices associated with a graph, such as the Laplacian and the distance matrix (for connected graphs) have also been studied. We explore algebraic properties of these various matrices associated with graphs, and explore in more detail the properties of the distance matrix which is not well-studied as the other two matrices.
A Mathematical Approach to Congressional Redistricting
Abby Brickner and Natalie Anderson
In this work, we investigate a genetic algorithm approach for creating optimal U.S. Congressional districts. The project quantifies the quality of redistricting plans according to four criteria: population equality, that each district contains approximately the same number of constituents; competitiveness, that districts produce as many competitive elections as possible; compactness, that districts resemble regular shapes; and fairness, that districts do not favor a particular political party. With partisan gerrymandering cases in courts across the country and capturing the attention of the public, our work provides an objective approach to measure how gerrymandered district plans are, and aims at designing fairer plans that preserve communities of interest. Perhaps more importantly with this mathematical framework, we are able to gain a deeper understanding of the redistricting process, as well as the impact it has on American society.