Files in this item
Files  Description  Format 

application/pdf ZamaniNasab_Reza.pdf (580kB)  (no description provided) 
Description
Title:  Hamiltonian cycles through specified edges in bipartite graphs, domination game, and the game of revolutionaries and spies 
Author(s):  Zamani Nasab, Reza 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  West, Douglas B. 
Doctoral Committee Member(s):  Kostochka, Alexandr V.; Chekuri, Chandra S.; Prabhakaran, Manoj; LaValle, Steven M. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  hamiltonian cycle
bipartite graph specified edges domination game the game of revolutionaries and spies 
Abstract:  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 degreesum 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 degreesum 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{Stallerfirst 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 2k1$, 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 twoplayer 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$. 
Issue Date:  20110825 
URI:  http://hdl.handle.net/2142/26187 
Rights Information:  Copyright 2011 Reza Zamani Nasab 
Date Available in IDEALS:  20110825 
Date Deposited:  201108 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois