Search

A variation of the Cops and Robber game is introduced in which the robber side consists of two robbers. The cops win by moving onto the same vertex as one of the robbers after a finite number of moves. As in the original game, the robber side can win by avoiding capture indefinitely. In this version, however, the robbers can also win by both moving onto the same vertex as the cop at the same time. Otherwise, the robbers must be located on distinct vertices. We present structural properties of ambush-copwin graphs, those graphs on which a single cop can guarantee a win. As well, we characterize ambush-copwin graphs of girth $$g \ge 4$$ and classes of ambush-copwin graphs of girth 3, particularly a class of chordal graphs.

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 robber’s neighbouring vertices. We denote by σ ( G ) the 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.

We consider a variation of the Cops and Robber game where the cops can only see the robber when the distance between them is at most a fixed parameter l . We consider the basic consequences of this definition for some simple graph families, and show that this model is not monotonic, unlike common models where the robber is invisible. We see that cops’ strategy consists of a phase in which they need to “see” the robber (move within distance l of the robber), followed by a phase in which they capture the robber. In some graphs the first phase is the most resource intensive phase (in terms of number of cops needed), while in other graphs, it is the second phase. Finally, we characterize those trees for which k cops are sufficient to guarantee capture of the robber for all l ≥ 1 .

The dominating graph of a graph $H$ has as its vertices all dominating sets of $H$, with an edge between two dominating sets if one can be obtained from the other by the addition or deletion of a single vertex of $H$. In this paper we prove that the dominating graph of any tree has a Hamilton path. We also show how a result about binary strings leads to a proof that the dominating graph of a cycle on $n$ vertices has a Hamilton path if and only if $n\not\equiv 0 \pmod 4$.

The dominating graph of a graph G has as its vertices all dominating sets of G, with an edge between two dominating sets if one can be obtained from the other by adding or deleting a single vertex of G. This is an example of a reconfiguration graph. This paper gives a brief introduction to the study of reconfiguration of dominating sets, and to the dominating graph. We highlight some previous results and present some new work. In particular we give new results on the existence of Hamilton paths in the dominating graph.

For a fixed integer t, a set of vertices B of a graph G is a t-limited packing of G provided that the closed neighbourhood of any vertex in G contains at most t elements of B. The size of a largest possible t-limited packing in G is denoted Lt(G) and is the t-limited packing number of G. In this paper, we investigate the 2-limited packing number of Cartesian products of paths. We show that for fixed k the difference L2(PkPn)L2(PkPn1) is eventually periodic as a function of n, and thereby give closed formulas for L2(PkPn), k=1,2,,5. The techniques we use are suitable for establishing other types of packing and domination numbers for Cartesian products of paths and, more generally, for graphs of the form HPn.

We introduce a new variant of the game of Cops and Robbers played on graphs, where the robber is invisible unless outside the neighbor set of a cop. The hyperopic cop number is the corresponding analogue of the cop number, and we investigate bounds and other properties of this parameter. We characterize the cop-win graphs for this variant, along with graphs with the largest possible hyperopic cop number. We analyze the cases of graphs with diameter 2 or at least 3, focusing on when the hyperopic cop number is at most one greater than the cop number. We show that for planar graphs, as with the usual cop number, the hyperopic cop number is at most 3. The hyperopic cop number is considered for countable graphs, and it is shown that for connected chains of graphs, the hyperopic cop density can be any real number in [ 0 , 1 / 2 ] .

The need for high-quality, large-scale, goal-oriented dialogue datasets continues to grow as virtual assistants become increasingly wide-spread. However, publicly available datasets useful for this area are limited either in their size, linguistic diversity, domain coverage, or annotation granularity. In this paper, we present strategies toward curating and annotating large scale goal oriented dialogue data. We introduce the MultiDoGO dataset to overcome these limitations. With a total of over 81K dialogues harvested across six domains, MultiDoGO is over 8 times the size of MultiWOZ, the other largest comparable dialogue dataset currently available to the public. Over 54K of these harvested conversations are annotated for intent classes and slot labels. We adopt a Wizard-of-Oz approach wherein a crowd-sourced worker (the “customer”) is paired with a trained annotator (the “agent”). The data curation process was controlled via biases to ensure a diversity in dialogue flows following variable dialogue policies. We provide distinct class label tags for agents vs. customer utterances, along with applicable slot labels. We also compare and contrast our strategies on annotation granularity, i.e. turn vs. sentence level. Furthermore, we compare and contrast annotations curated by leveraging professional annotators vs the crowd. We believe our strategies for eliciting and annotating such a dialogue dataset scales across modalities and domains and potentially languages in the future. To demonstrate the efficacy of our devised strategies we establish neural baselines for classification on the agent and customer utterances as well as slot labeling for each domain.

A proper colouring is referred to as a Grundy colouring, or first-fit colouring if every vertex has a neighbour from each of the colour classes lower than its own. The Grundy number of a graph is the maximum k (number of colours) such that a Grundy colouring exists.In this note, we determine lower and upper bounds for the Grundy number of strong products of graphs, which lead to exact values for the product of some graph classes. We also provide an upper bound on the Grundy number of the strong product of n paths of length 2, which generalizes to an upper bound on the Grundy number of the strong product of n stars.

We describe a simple method for computing the maximum length of the game cop and robber, assuming optimal play for both sides.

We give two characterizations of the graphs on which k cops have a winning strategy in the game of Cops and Robber. One of these is in terms of an order relation, and one is in terms of a vertex ordering. Both generalize characterizations known for the case k=1.

The games considered are mixtures of Searching and Cops and Robber. The cops have partial information provided via witnesses who report ''sightings'' of the robber. The witnesses are able to provide information about the robber's position but not the direction in which he is moving. The robber has perfect information. In the case when sightings occur at regular intervals, we present a recognition theorem for graphs on which a single cop suffices to guarantee a win. In a special case, this recognition theorem provides a characterization.

The indirect method error-choice technique was adapted to develop the ADA Information Survey (ADA-IS), which assessed the attitude of 57 master's level rehabilitation counseling students, 62 college students with disabilities, and 83 small business employers, toward the Americans with Disabilities Act (ADA) Title I. Students with disabilities held the most favorable attitudes; rehabilitation counseling students' attitudes were more favorable than employers' attitudes. The construct validity and reliability of the ADA-IS were examined. Discussion of and suggestions for using the ADA-IS for advocacy and educational purposes and for future research are presented.

The Cops and Robber game is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if they can catch the robber. The minimum number of cops needed to win on a graph is called its cop number. It is known that the cop number of a graph embedded on a surface $X$ of genus $g$ is at most $3g/2 + 3$, if $X$ is orientable (Schroeder 2004), and at most $2g+1$, otherwise (Nowakowski & Schroeder 1997). We improve the bounds for non-orientable surfaces by reduction to the orientable case using covering spaces. As corollaries, using Schroeder's results, we obtain the following: the maximum cop number of graphs embeddable in the projective plane is 3; the cop number of graphs embeddable in the Klein Bottle is at most 4, and an upper bound is $3g/2 + 3/2$ for all other $g$., 5 pages, 1 figure

In this version of the Cops and Robber game, the cops move in tandems, or pairs, such that they are at distance at most one after every move. We present a recognition theorem for tandem-win graphs, and a characterization of triangle-free tandem-win graphs.

We consider edge critical graphs when playing cops and robber. Specifically, we look at those graphs whose copnumbers change from one to two when any edge is added, deleted, subdivided or contracted. We characterize all such sets, showing that they are empty, trees, all 2-edge-connected graphs and empty, respectively. We also consider those graphs which change from copnumber two to one when any edge is added, and give a characterization in the k-regular case.