1/1
3 files

Strategies in the Game F-Saturator

presentation
posted on 13.10.2014, 00:00 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

Usage metrics

UGRD 2013

Keywords

Licence

Exports