University of Wyoming
Browse
UGRD_2013_Spring_Oursler_Roy.pdf (225.74 kB)

Strategies in the Game F-Saturator

Download (225.74 kB)
presentation
posted on 2021-11-15, 18:25 authored by Roy Oursler
In mathematics, a graph is a set of vertices and a set of edges which connect pairs of vertices. A subgraph is graph that is a subset of vertices of a graph and a subset of the edges connecting those vertices. Some example graphs can be made drawing dots (vertices) on a piece of paper and drawing lines (edges) between those dots. Let F be a graph. The game F-Saturator is played by two players who take turns adding edges to a graph G. A player loses if after their move, F is a subgraph of G. For example, a triangle could be F, and if a player adds an edge which completes a triangle, that player loses. This game is a tool to increase understanding of F-saturated graphs. An F-saturated graph is a graph which does not contain some subgraph F, but the addition of any edge to that graph creates the subgraph F. In this presentation, I analyze some versions of F-Saturator to determine which player wins and discuss the challenges of determining the winner through brute force computation.

History

Advisor

Williford, Jason

ISO

eng

Language

English

Publisher

University of Wyoming. Libraries

Department

  • Library Sciences - LIBS

Usage metrics

    UGRD 2013

    Keywords

    Licence

    Exports