Back

# Mathematics Presentations

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.