Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMarkov models for the tipsy cop and robber game on graphs
72
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we analyze and model three open problems posed by Harris, Insko, Prieto-Langarica, Stoisavljevic, and Sullivan in 2020 concerning the tipsy cop and robber game on graphs. The three different scenarios we model account for different biological scenarios. The first scenario is when the cop and robber have a consistent tipsiness level though the duration of the game; the second is when the cop and robber sober up as a function of time; the third is when the cop and robber sober up as a function of the distance between them. Using Markov chains to model each scenario we calculate the probability of a game persisting through $mathbf{M}$ rounds of the game and the expected game length given different starting positions and tipsiness levels for the cop and robber.
rate research
Read More
Motivated by a biological scenario illustrated in the YouTube video url{ https://www.youtube.com/watch?v=Z_mXDvZQ6dU} where a neutrophil chases a bacteria cell moving in random directions, we present a variant of the cop and robber game on graphs called the tipsy cop and drunken robber game. In this game, we place a tipsy cop and a drunken robber at different vertices of a finite connected graph $G$. The game consists of independent moves where the robber begins the game by moving to an adjacent vertex from where he began, this is then followed by the cop moving to an adjacent vertex from where she began. Since the robber is inebriated, he takes random walks on the graph, while the cop being tipsy means that her movements are sometimes random and sometimes intentional. Our main results give formulas for the probability that the robber is still free from capture after $m$ moves of this game on highly symmetric graphs, such as the complete graphs, complete bipartite graphs, and cycle graphs. We also give the expected encounter time between the cop and robber for these families of graphs. We end the manuscript by presenting a general method for computing such probabilities and also detail a variety of directions for future research.
We show that the cop number of every generalized Petersen graph is at most 4. The strategy is to play a modified game of cops and robbers on an infinite cyclic covering space where the objective is to capture the robber or force the robber towards an end of the infinite graph. We prove that finite isometric subtrees are 1-guardable and apply this to determine the exact cop number of some families of generalized Petersen graphs. We also extend these ideas to prove that the cop number of any connected I-graph is at most 5.
We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter $zeta(G)$ for a given graph $G$ is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of $zeta(G)$. Moreover, we extend the argument to sparse graphs.
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, ODonnel, Tamuz and Tan conjectured that, in the ErdH{o}s--Renyi random graph $G(n,p)$, the random initial $pm 1$-assignment converges to a $99%$-agreement with high probability whenever $p=omega(1/n)$. This conjecture was first confirmed for $pgeqlambda n^{-1/2}$ for a large constant $lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< lambda n^{-1/2}$. We break this $Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $lambda n^{-3/5}log n leq p leq lambda n^{-1/2}$ with a large constant $lambda>0$.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
