Hamiltonian cycles through specified edges in bipartite graphs, domination game, and the game of revolutionaries and spies

This thesis deals with the following three independent problems.;Posa 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 + tau(F), where tau( F) = &ceill0;k/2&ceilr0; + epsilon (here epsilon = 1 if t1 = 0 or if (t1, t2) ∈ {(1, 0), (2, 0)}, and epsilon = 0 otherwise). We show also that this threshold on the degree-sum is sharp when n > 3k..;Bostjan Bresar, Sandi Klavzar 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. The game ends when the occupied set becomes a dominating set (A dominating set is a set of vertices U such that every vertex is in U or has a neighbor in U; the minimum size of a dominating set is the domination number, written gamma( G)). Dominator's goal is to finish the game as soon as possible, and Staller's goal is to prolong it as much as possible. The size of the dominating set obtained when both players play optimally is the game domination number of G, written as gammag( G). The Staller-first game domination number, written as g'g (G), is defined similarly; the only difference is that Staller starts the game. Bresar et al. showed that gamma( G) ≤ gammag(G) ≤ 2gamma(G) -- 1 and that for any k and k' such that k ≤ k' ≤ 2k -- 1, there exists a graph G with gamma( G) = k and gammag( G) = k'. Their constructions use graphs with many vertices of degree 1. We present an n-vertex graph G with domination number, minimum degree and connectivity of order theta( n ) that satisfies gammag(G) = 2gamma(G) -- 1. Building on the work of Bresar et al., Kinnersley proved that |gammag( G) -- g'g (G)| ≤ 1. Bresar et al. defined a pair (k, k') to be realizable if gammag(G) = k and g'g (G) = k' for some graph G. They showed that the pairs (k, k), (k, k + 1) and (2k + 1, 2k) are realizable for k ≥ 1. Their constructions for (k, k + 1) and (2k + 1, 2k) are not connected. We show that for k ≥ 1, the pairs (k, k + 1), (2k + 1, 2k) and (2k + 2, 2k + 1) are realizable by connected graphs.;Jozef Beck invented the following game, the game of revolutionaries and spies. It is a two-player game RS (G, m, r, s) played on a graph G by two players R and S . Player R controls r pieces called revolutionaries and player S controls s pieces called spies. At the start, R places his pieces on vertices of G, and then S does so also. At each subsequent round, R moves some of his pieces from their current vertex to a neighboring vertex, and then S does so also. If at the end of a round there is a meeting of at least m revolutionaries on some vertex without a spy, then R wins. Player S wins if he can prevent such a meeting forever. We show that s ≥ gamma(G) &fll0;r/m&flr0; suffices for S to win RS (G, m, r, s). Given r and s, let H be a complete bipartite graph with at least r + s vertices in each partite set. We will show that 7r/10 + O(1) is the minimum number of spies needed to win RS (H, 2, r, s). We also show r/2 + O(1) is the minimum number of spies needed to win RS (H, 3, r, s). For m ≥ 4, we show that the minimum number of required spies to win RS (H, m, r, s) is at least &fll0;&fll0;r/2&flr0;/&ceill0;m/3&ceilr0;&flr0; -- 1 and at most (1 + 1/ 3 )r/m + 1.