Hamiltonian cycles through specified edges in bipartite graphs, domination game, and the game of revolutionaries and spies
Reza Zamani Nasab · 2011
This thesis deals with the following three independent problems. Pósa proved that if G is an n-vertex graph in which any two nonadjacent vertices have degree sum at least n + k, then G has a spanning cycle containing any specified family of disjoint paths with a total of k edges. We consider the analogous problem for a bipartite graph G with n vertices and parts of equal size. Let F be a subgraph of G whose components are nontrivial paths. Let k be the number of edges in F, and let t1 and t2 be the numbers of components of F having odd and even length, respectively. We prove that G has a spanning cycle containing F if any two nonadjacent vertices in opposite partite sets have degree-sum at least n/2+τ(F), where τ(F) = ⌈k/2⌉+ɛ (here ɛ = 1 if t1 = 0 or if (t1, t2) ∈ {(1, 0), (2, 0)}, and ɛ = 0 otherwise). We show also that this threshold on the degree-sum is sharp when n> 3k. Bostjan Breˇsar, Sandi Klavˇzar and Douglas F. Rall proposed a game involving the notion of graph domination number. Two players, Dominator and Staller, occupy vertices of a graph G, playing alternatingly. Dominator starts first. A vertex is valid is to be occupied if adding it to the occupied set enlarges the set of vertices dominated by the occupied set.