اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCops that surround a robber
44
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 cal
led 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 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 co
ntaining 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})$.
A well-known combinatorial theorem says that a set of n non-collinear points in the plane determines at least n distinct lines. Chen and Chvatal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this
work we prove a slightly stronger version of Chen and Chvatal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.
A propositional logic sentence in conjunctive normal form that has clauses of length two (a 2-CNF) can be associated with a multigraph in which the vertices correspond to the variables and edges to clauses. We first show that every such sentence that
has been reduced, that is, which is unchanged under application of certain tautologies, is equisatisfiable to a 2-CNF whose associated multigraph is, in fact, a simple graph. Our main result is a complete characterization of graphs that can support unsatisfiable 2-CNF sentences. We show that a simple graph can support an unsatisfiable reduced 2-CNF sentence if and only if it contains any one of four specific small graphs as a topological minor. Equivalently, all reduced 2-CNF sentences supported on a given simple graph are satisfiable if and only if all subdivisions of those four graphs are forbidden as subgraphs of of the original graph. We conclude with a discussion of why the Robertson-Seymour graph minor theorem does not apply in our approach.
A binary poset code of codimension M (of cardinality 2^{N-M}, where N is the code length) can correct maximum M errors. All possible poset metrics that allow codes of codimension M to be M-, (M-1)- or (M-2)-perfect are described. Some general conditi
ons on a poset which guarantee the nonexistence of perfect poset codes are derived; as examples, we prove the nonexistence of R-perfect poset codes for some R in the case of the crown poset and in the case of the union of disjoin chains. Index terms: perfect codes, poset codes
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
