Peg solitaire is a game in which pegs are placed in every hole but one and the player jumps over pegs along rows or columns to remove them. Usually, the goal is to have a single peg remaining. In a 2011 paper, this game is generalized to graphs. In this paper, we consider a variation in which each peg must be jumped twice in order to be removed. For this variation, we consider the solvability of several graph families. For our major results, we characterize solvable joins of graphs and show that the Cartesian product of solvable graphs is likewise solvable.

Peg solitaire is a game in which pegs are placed in every hole but one and the player jumps over pegs along rows or columns to remove them. Usually, the goal of the player is to leave only one peg. In a 2011 paper, this game is generalized to graphs. In this thesis, we consider a variation of peg solitaire on graphs in which pegs can be removed either by jumping them or merging them together. To motivate this, we survey some of the previous papers in the literature. We then determine the solvability of several classes of graphs including stars and double stars, caterpillars, trees of small diameter, particularly four and five, and articulated caterpillars. We conclude this thesis with several open problems related to this study.

Peg solitaire is a game in which pegs are placed in every hole but one and the player jumps over pegs along rows or columns to remove them. Usually, the goal of the player is to leave only one peg. In a 2011 paper, this game is generalized to graphs. When the game is played between two players it is called duotaire. In this paper, we consider two variations of peg duotaire on graphs. In the first variation, the last player to remove a peg wins. Inspired by the work of Slater, we also investigate a variation in which one player tries to maximize the number of pegs at the end of the game while their opponent seeks to minimize this number. For both variations, we give explicit strategies for several families of graphs. Finally, we give a number of open problems as possible avenues for future research.

In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.

Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects. Much of the thesis is concerned with the computational complexity of problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic ("flood" the graph) with the minimum possible number of flooding operations; such problems are known to be computationally hard in many cases. We begin by proving some general structural results about the behaviour of the game, including a powerful characterisation of the number of moves required to flood a graph in terms of the number of moves required to flood its spanning trees; these structural results are then applied to prove tractability results about a number of flood-filling problems. We also consider the computational complexity of flood-filling problems when the game is played on a rectangular grid of fixed height (focussing in particular on 3xn and 2xn grids), answering an open question of Clifford, Jalsenius, Montanaro and Sach. The final chapter concerns the parameterised complexity of list problems on graphs of bounded treewidth. We prove structural results determining the list edge chromatic number and list total chromatic number of graphs with bounded treewidth and large maximum degree, which are special cases of the List (Edge) Colouring Conjecture and Total Colouring Conjecture respectively. Using these results, we show that the problem of determining either of these quantities is fixed parameter tractable, parameterised by the treewidth of the input graph. Finally, we analyse a list version of the Hamilton Path problem, and prove it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.

<p>\section*{Abstract}<br />We study Maker-Breaker games played on the edges of the complete graph on $n$ vertices, $K_n$, whose family of winning sets $\cF$ consists of all edge sets of subgraphs $G\subseteq K_n$ which possess a predetermined monotone increasing property. Two players, Maker and Breaker, take turns in claiming $a$, respectively $b$, unclaimed edges per move. We are interested in finding the threshold bias $b_{\cF}(a)$ for all values of $a$, so that for every $b$, $b\leq b_{\cF}(a)$, Maker wins the game and for all values of $b$, such that $b&gt;b_{\cF}(a)$, Breaker wins the game. We are particularly interested in cases where both $a$ and $b$ can be greater than $1$. We focus on the \textit{Connectivity game}, where the winning sets are the edge sets of all spanning trees of $K_n$ and on the&nbsp; \textit{Hamiltonicity game}, where the winning sets are the edge sets of all Hamilton cycles on $K_n$.<br /><br />Next, we consider biased $(1:b)$ Avoider-Enforcer games, also played on the edges of $K_n$. For every constant $k\geq 3$ we analyse the $k$-star game, where Avoider tries<br />to avoid claiming $k$ edges incident to the same vertex. We analyse both versions of Avoider-Enforcer games, the strict and the monotone, and for each provide explicit winning strategies for both players. Consequentially, we establish bounds on the threshold biases $f^{mon}_\cF$, $f^-_\cF$ and $f^+_\cF$, where $\cF$ is the hypergraph of the game (the family of target sets).<br />We also study the monotone version of $K_{2,2}$-game, where Avoider wants to avoid claiming all the edges of some graph isomorphic to $K_{2,2}$ in $K_n$.&nbsp;&nbsp;</p><p>Finally, we search for the fast winning strategies for Maker in Perfect matching game and Hamiltonicity game, again played on the edge set of $K_n$. Here, we look at the biased $(1:b)$ games, where Maker&#39;s bias is 1, and Breaker&#39;s bias is $b, b\ge 1$.</p> / <p>\section*{Izvod}</p><p>Prou\v{c}avamo takozvane Mejker-Brejker (Maker-Breaker) igre koje se igraju na granama kompletnog grafa sa $n$ \v{c}vorova, $K_n$, \v{c}ija familija pobedni\v{c}kih skupova $\cF$ obuhvata sve skupove grana grafa $G\subseteq K_n$ koji imaju neku monotono rastu\&#39;{c}u osobinu. Dva igra\v{c}a, \textit{Mejker} (\textit{Pravi\v{s}a}) i \textit{Brejker} (\textit{Kva\-ri\-\v{s}a}) se smenjuju u odabiru $a$, odnosno $b$, slobodnih grana po potezu. Interesuje nas da prona\dj emo grani\v{c}ni bias $b_{\cF}(a)$ za sve vrednosti pa\-ra\-me\-tra $a$, tako da za svako $b$, $b\le b_{\cF}(a)$, Mejker pobe\dj uje u igri, a za svako $b$, takvo da je $b&gt;b_{\cF}(a)$, Brejker pobe\dj uje. Posebno nas interesuju slu\v{c}ajevi u kojima oba parametra $a$ i $b$ mogu imati vrednost ve\&#39;cu od 1. Na\v{s}a pa\v{z}nja je posve\&#39;{c}ena igri povezanosti, gde su pobedni\v{c}ki skupovi&nbsp; grane svih pokrivaju\&#39;cih stabala grafa $K_n$, kao i igri Hamiltonove konture, gde su pobedni\v{c}ki skupovi grane svih Hamiltonovih kontura grafa $K_n$.</p><p>Zatim posmatramo igre tipa Avojder-Enforser (Avoider-Enforcer), sa biasom $(1:b)$, koje se tako\dj e igraju na granama kompletnog grafa sa $n$ \v{c}vorova, $K_n$. Za svaku konstantu $k$, $k\ge 3$ analiziramo igru $k$-zvezde (zvezde sa $k$ krakova), u kojoj \textit{Avojder} poku\v{s}va da izbegne da ima $k$ svojih grana incidentnih sa istim \v{c}vorom. Posmatramo obe verzije ove igre, striktnu i monotonu, i za svaku dajemo eksplicitnu pobedni\v{c}ku strategiju za oba igra\v{c}a. Kao rezultat, dobijamo gornje i donje ograni\v{c}enje za grani\v{c}ne biase $f^{mon}_\cF$, $f^-_\cF$ i $f^+_\cF$, gde $\cF$ predstavlja hipergraf igre (familija ciljnih skupova).<br />%$f^{mon}$, $f^-$ and $f^+$.<br />Tako\dj e, posmatramo i monotonu verziju $K_{2,2}$-igre, gde Avojder \v{z}eli da izbegne da graf koji \v{c}ine njegove grane sadr\v{z}i graf izomorfan sa $K_{2,2}$.</p><p>Kona\v{c}no, \v{z}elimo da prona\dj emo strategije za brzu pobedu Mejkera u igrama savr\v{s}enog me\v{c}inga i Hamiltonove konture, koje se tako\dj e igraju na granama kompletnog grafa $K_n$. Ovde posmatramo asimetri\v{c}ne igre gde je bias Mejkera 1, a bias Brejkera $b$, $b\ge 1$.</p>