Hamiltonian games (Q915667): Difference between revisions

Let \(K_ n\) be the complete graph of order n. Two players, maker and breaker, alternately take previously untaken edges of \(K_ n\), one edge per move, with the breaker going first. The game ends when all edges of \(K_ n\) have been taken. Then the edges taken by the maker induce a graph G. The maker wants G to have as many edge-disjoint Hamiltonian cycles as possible, and the breaker wants G to have as few edge-disjoint Hamiltonian cycles as possible. We prove that the maker can achieve ((1/16)-o(1))n edge-disjoint Hamiltonian cycles. We prove a similar result for the avoidance game and also give a new sufficient condition for a graph to be Hamiltonian.