Connected, bounded degree, triangle avoidance games (Q640454): Difference between revisions

Summary: We consider variants of the triangle-avoidance game first defined by Harary and rediscovered by Hajnal a few years later. A graph game begins with two players and an empty graph on \(n\) vertices. The two players take turns choosing edges within \(K_n\), building up a simple graph. The edges must be chosen according to a set of restrictions \(\mathcal R\). The winner is the last player to choose an edge that does not violate any of the restrictions in \(\mathcal R\). For fixed \(n\) and \(\mathcal R\), one of the players has a winning strategy. For a pair of games where \(\mathcal R\) includes bounded degree, connectedness, and triangle-avoidance, we determine the winner for all values of \(n\).