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. Po'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 $t_1$ and $t_2$ 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)=\ceil{k/2}+\epsilon$ (here $\epsilon=1$ if $t_1=0$ or if $(t_1,t_2)\in\{(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 \emph{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 \emph{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 \emph{game domination number} of $G$, written as $\gd(G)$. The \emph{Staller-first game domination number}, written as $\gd'(G)$, is defined similarly; the only difference is that Staller starts the game. Bre\v{s}ar \etal showed that $\gamma(G)\le\gd(G)\le 2\gamma(G)-1$ and that for any $k$ and $k'$ such that $k\le k'\le 2k-1$, there exists a graph $G$ with $\gamma(G)=k$ and $\gd(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(\sqrt{n})$ that satisfies $\gd(G)=2\gamma(G)-1$. Building on the work of Bre\v{s}ar et al., Kinnersley proved that $|\gd(G)-\gd'(G)|\le 1$. Bre\v{s}ar \etal defined a pair $(k,k')$ to be \emph{realizable} if $\gd(G)=k$ and $\gd'(G)=k'$ for some graph $G$. They showed that the pairs $(k,k)$, $(k,k+1)$ and $(2k+1,2k)$ are realizable for $k\ge 1$. Their constructions for $(k,k+1)$ and $(2k+1,2k)$ are not connected. We show that for $k\ge 1$, the pairs $(k,k+1)$, $(2k+1,2k)$ and $(2k+2,2k+1)$ are realizable by connected graphs. Jo'zef Beck invented the following game, the game of \emph{\revs and spies}. It is a two-player game $\rs(G,m,r,s)$ played on a graph $G$ by two players $\Rv$ and $\Sp$. Player $\Rv$ controls $r$ pieces called \emph{\revs} and player $\Sp$ controls $s$ pieces called \emph{spies}. At the start, $\Rv$ places his pieces on vertices of $G$, and then $\Sp$ does so also. At each subsequent round, $\Rv$ moves some of his pieces from their current vertex to a neighboring vertex, and then $\Sp$ does so also. If at the end of a round there is a meeting of at least $m$ \revs on some vertex without a spy, then $\Rv$ wins. Player $\Sp$ wins if he can prevent such a meeting forever. We show that $s\ge \gamma(G)\floor{r/m}$ suffices for $\Sp$ 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\ge 4$, we show that the minimum number of required spies to win $\rs(H,m,r,s)$ is at least $\bigfloor{\floor{r/2} / \ceil{m/3}}-1$ and at most $(1+{1/ \sqrt{3}}){r/ m}+1$