اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدContainment: A Variation of Cops and Robbers
120
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider Containment: a variation of the graph pursuit game of Cops and Robber in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop), and the cops win by containing the robber---that is, by occupying all $deg(v)$ of the edges incident with a vertex $v$ while the robber is at $v$. We develop bounds that relate the minimal number of cops, $xi(G)$, required to contain a robber to the well-known cop-number $c(G)$ in the original game: in particular, $c(G) {le} xi(G) {le} gamma(G) Delta(G)$. We note that $xi(G) {geq} delta(G)$ for all graphs $G$, and analyze several families of graphs in which equality holds, as well as several in which the inequality is strict. We also give examples of graphs which require an unbounded number of cops in order to contain a robber, and note that there exist cubic graphs with $xi(G) geq Omega(n^{1/6})$.
قيم البحث
اقرأ أيضاً
We introduce the game of Surrounding Cops and Robbers on a graph, as a variant of the original game of Cops and Robbers. In contrast to the original game in which the cops win by occupying the same vertex as the robber, they now win by occupying each
of the robbers neighbouring vertices. We denote by $sigma(G)$ the {em surrounding cop number} of $G$, namely the least number of cops required to surround a robber in the graph $G$. We present a number of results regarding this parameter, including general bounds as well as exact values for several classes of graphs. Particular classes of interest include product graphs, graphs arising from combinatorial designs, and generalised Petersen graphs.
The study of pattern containment and avoidance for linear permutations is a well-established area of enumerative combinatorics. A cyclic permutation is the set of all rotations of a linear permutation. Callan initiated the study of permutation avoida
nce in cyclic permutations and characterized the avoidance classes for all single permutations of length 4. We continue this work. In particular, we establish a cyclic variant of the Erdos-Szekeres Theorem that any linear permutation of length mn+1 must contain either the increasing pattern of length m+1 or the decreasing pattern of length n+1. We then derive results about avoidance of multiple patterns of length 4. We also determine generating functions for the cyclic descent statistic on these classes. Finally, we end with various open questions and avenues for future research.
Every word has a shape determined by its image under the Robinson-Schensted-Knuth correspondence. We show that when a word w contains a separable (i.e., 3142- and 2413-avoiding) permutation sigma as a pattern, the shape of w contains the shape of sig
ma. As an application, we exhibit lower bounds for the lengths of supersequences of sets containing separable permutations.
Several variations of hat guessing games have been popularly discussed in recreational mathematics. In a typical hat guessing game, after initially coordinating a strategy, each of $n$ players is assigned a hat from a given color set. Simultaneously,
each player tries to guess the color of his/her own hat by looking at colors of hats worn by other players. In this paper, we consider a new variation of this game, in which we require at least $k$ correct guesses and no wrong guess for the players to win the game, but they can choose to pass. A strategy is called {em perfect} if it can achieve the simple upper bound $frac{n}{n+k}$ of the winning probability. We present sufficient and necessary condition on the parameters $n$ and $k$ for the existence of perfect strategy in the hat guessing games. In fact for any fixed parameter $k$, the existence of perfect strategy can be determined for every sufficiently large $n$. In our construction we introduce a new notion: $(d_1,d_2)$-regular partition of the boolean hypercube, which is worth to study in its own right. For example, it is related to the $k$-dominating set of the hypercube. It also might be interesting in coding theory. The existence of $(d_1,d_2)$-regular partition is explored in the paper and the existence of perfect $k$-dominating set follows as a corollary.
We model the hierarchical evolution of an organized criminal network via antagonistic recruitment and pursuit processes. Within the recruitment phase, a criminal kingpin enlists new members into the network, who in turn seek out other affiliates. New
recruits are linked to established criminals according to a probability distribution that depends on the current network structure. At the same time, law enforcement agents attempt to dismantle the growing organization using pursuit strategies that initiate on the lower level nodes and that unfold as self-avoiding random walks. The global details of the organization are unknown to law enforcement, who must explore the hierarchy node by node. We halt the pursuit when certain local criteria of the network are uncovered, encoding if and when an arrest is made; the criminal network is assumed to be eradicated if the kingpin is arrested. We first analyze recruitment and study the large scale properties of the growing network; later we add pursuit and use numerical simulations to study the eradication probability in the case of three pursuit strategies, the time to first eradication and related costs. Within the context of this model, we find that eradication becomes increasingly costly as the network increases in size and that the optimal way of arresting the kingpin is to intervene at the early stages of network formation. We discuss our results in the context of dark network disruption and their implications on possible law enforcement strategies.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
