Research Paper
Year: 2023 | Month: July-September | Volume: 7 | Issue: 3 | Pages: 31-37
DOI: https://doi.org/10.52403/gijash.20230304
Patterns and Line-Adjacency Matrix Strategy on a Game of Induced Matching
Yaqi Li
North Carolina School of Science and Math, Durham, NC
Corresponding Author: yaqilius@gmail.com
ABSTRACT
A matching is an independent set of edges in a graph G; an induced matching is a matching with an additional property that no two of its edges are joined by an edge in G. An induced matching M in a graph G is maximal if no other induced matching in G contains M. In the proposed game, players alternate choose edges on a graph while maintaining an induced matching. They continue until the matching is maximal (i.e. no player can choose another edge), and the last player to choose an edge wins. This paper will discuss patterns for this game and prove results on several categories of graphs including Complete Graphs, Path Graphs, Cycle Graphs, and Ladder Graphs. In addition, a novel Line-Adjacency Matrix method has been defined and proved to calculate all possible edges for the next move in a connected graph.
Keywords: Induced Matching, Adjacency Matrix, Line-Adjacency Graph
[PDF Full Text]