Presentations are listed in alphabetical order by the presenter's last name.

The Firefighter Problem

The Firefighter Problem introduced by Bert Hartnell in 1995 proposes there will be an outbreak of a fire at a specific vertex in the graph. The job of the firefighter will be to defend a vertex. The fire will then spread to adjacent vertices that are not defended, which causes the firefighter to defend another vertex and the process continues until the fire is contained. The underlying idea of the Firefighter Problem is to optimize resources and preventative measures in case of an emergency. Finite square grids of dimension 2 or 3 have been researched within the context of the Firefighter Problem. The Cartesian products of two path graphs is $P_n$$\square$$P_n$. There is a proposition that provides an ordering of the vertices in this graph to maximize the number of saved vertices. Using this research, we investigate an optimal strategy for defending a fire in $P_n \square P_m$ where the paths have different lengths and extend these ideas to cycles.

Presenters: Megan Black, Joshua Spiers and Samantha Vanderlipp / Mentor: Jonelle Hook, Ph.D.

Hamiltonian Graphs

An Euler circuit in a graph is a cycle that uses each edge exactly once. A Hamiltonian cycle in a graph is a cycle that uses each vertex exactly once. Euler proved that any graph whose vertices are all even degree has an Eulerian circuit. Currently, there is no theorem that determines when a graph has a Hamiltonian cycle, but there are certain conditions one may check to see if the graph has a Hamiltonian cycle. The Traveling Salesperson Problem is an example of an application of Hamiltonian cycles. We explore various applications of Hamiltonian cycles and Eulerian circuits on multiple platforms including games.

Presenters: Rebecca Breiner and Olivia Gardenhour / Mentor: Jonelle Hook, Ph.D.

Mine Sweeper Solver

A tree in graph theory is a connected graph with no cycles. We seek to create a Mine Sweeper solver program. The solution to this game can be found with a series of advanced searches in the realm of applying mathematics to computer science. Trees, the topic in graph theory, will be applied to computer science such that we can search for desired results efficiently. We will most likely use a series of breadth first or depth first searches mixed in with some heuristics in order to find a solution to each and every possible game of Mine Sweeper presented to our solver.

Presenter: Joseph Contreras / Mentor: Jonelle Hook, Ph.D.

Super Magic Bipartite Directed Graphs

A super magic graph is a graph whose edges are labeled using the entries of a magic square. The edges are labeled in such a way that the labels of incident edges sum to the same value at the shared vertex. Super magic bipartite graphs can also be viewed as a directed graph by adding the number if an arrow points in and subtracting the number it if the arrow is pointing out for each vertex sum. This project explores the relationship between digraphs and magic graphs. More speciﬁcally, I am looking at a bipartite super magic graph in search of a pattern depending on the direction of the edges given that the edges have the labeling of a magic square. The initial exploration begins at K3,3 and continues to the general bipartite graph on 2n vertices.

Presenter: Emily Eckard / Mentor: Jonelle Hook, Ph.D.

Graceful Labelings and Greedy Algorithms

A graph is a collection of vertices and edges where a single edge connects two vertices. Graph labeling is the assignment of labels, often integers, to the vertices, edges, or both, of a graph. There are various kinds of labelings, one of which is graceful labeling. A graph of m vertices and n edges is gracefully labeled when vertices are assigned a label from 0 to m and the edges are assigned a label between 1 to m+1. Edge labelings are determined by taking the absolute value of the difference between the labels on the vertices of an incident edge e; therefore, the labels on the edges are unique. While there are many graphs that are known to be graceful, we have found no general algorithms for labeling all types of graceful graphs. One type of algorithm used in a variety of graph theory topics is a greedy algorithm where you make the locally optimal choice at each step in order to find an optimal solution. We explore the application of a variation of a greedy algorithm on graphs that are known to be graceful. These results determine which types of graceful graphs can be labeled using a greedy algorithm.

Presenters: Cheyenne Norwood and Kevin Clark-Cuadrado / Mentor: Jonelle Hook, Ph.D.

Tournaments in Trees

The subgraph isomorphism problem asks whether we can find a copy of a graph H within another graph G, given two arbitrary graphs H and G. In particula , we are often interested in determining how large a dense graph must be before we can always find simpler structures within it. We will investigate embeddings of directed trees in tournament graphs, using a combination of randomized algorithms and graph theoretic techniques to analyze how we can always find any directed tree we wish, given any tournament that is only moderately larger. We explore how restricting our attention to simple types of trees lets us find efficient algorithms to an otherwise computationally hard problem, and how the question becomes easier to answer as we consider graphs that can be arbitrarily large.

Presenters: Cheyenne Norwood and Kevin Clark-Cuadrado / Mentor: Jonelle Hook, Ph.D.

Back to the Roots: Reversing Algorithms For Minimum Spanning Trees

A graph is considered a tree when there is the least amount of edges in the graph that still connects every vertex. A weighted graph is a graph in which each edge has a numerical weight associated with it. The weight of a tree is the sum of all its edge weights. Every graph has a minimum spanning tree which is the collection of edges that connect every vertex of the graph with total minimum weight. This can be found through various algorithms which include Prim's Algorithm, Boruvka's Algorithm, and Kruskal's Algorithm. This project will focus on the reversal of these algorithms to determine if the result is also a minimum spanning tree.

Presenters: Joseph Oleskey and Abigail Spencer / Mentor: Jonelle Hook, Ph.D.

Exclusions of Magic Labelings on Digraphs

A magic labeling on a graph assigns a distinct positive integer to every edge and vertex such that the sum of all labels incident with each vertex sums to the same magic number. Magic labelings can be applied to graphs with directed edges, which are called digraphs, in such a way that each edge's direction is taken into account when determining the magic number. Our research will focus on determining reasons why magic labelings do not exist for certain digraphs, ultimately seeking to generalize our findings into a set of rules for all magic labelings on digraphs. Our research will focus on specific known examples of anti-magic digraphs.

Presenters: Megan Zuvich and Matthew McDonald / Mentor: Jonelle Hook, Ph.D.

Presentations by Area of Study

Biochemistry Biology Business Chemistry Communication Computer Science Conflict, Peace and Social Justice Criminal Justice Economics Elementary Education English Environmental Science Health Sciences History Mathematics Philosophy, Politics and Economics (PPE) Political Science Psychology Secondary Education Sociology Theology