83 citations · 346 across the 78 of their papers we have counts for
12 papers · 1 filter
The acquaintance time of (percolated) random geometric graphs
Tobias Muller, Pawel Pralat
In this paper, we study the acquaintance time $\AC(G)$ defined for a connected graph . We focus on $\G(n,r,p)$, a random subgraph of a random geometric graph in which vertic…
Lazy Cops and Robbers played on Graphs
Deepak Bal, Anthony Bonato, William B. Kinnersley +1
We consider a variant of the game of Cops and Robbers, called Lazy Cops and Robbers, where at most one cop can move in any round. We investigate the analogue of the cop number for…
Models of on-line social networks
Anthony Bonato, Noor Hadi, Paul Horn +2
We present a deterministic model for on-line social networks (OSNs) based on transitivity and local knowledge in social interactions. In the Iterated Local Transitivity (ILT) model…
Vertex-pursuit in random directed acyclic graphs
Anthony Bonato, Dieter Mitsche, P. Pralat
We examine a dynamic model for the disruption of information flow in hierarchical social networks by considering the vertex-pursuit game Seepage played in directed acyclic graphs (…
The capture time of the hypercube
Anthony Bonato, William B. Kinnersley, P. Gordinowicz +1
In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the captu…
The robber strikes back
Anthony Bonato, Stephen Finbow, Przemyslaw Gordinowicz +5
We consider the new game of Cops and Attacking Robbers, which is identical to the usual Cops and Robbers game except that if the robber moves to a vertex containing a single cop, t…
Independence densities of hypergraphs
Anthony Bonato, Jason Brown, Dieter Mitsche +1
We consider the number of independent sets in hypergraphs, which allows us to define the independence density of countable hypergraphs. Hypergraph independence densities include a…
Toppling numbers of complete and random graphs
A. Bonato, W. Kinnersley, P. Pralat
We study a two-person game played on graphs based on the widely studied chip-firing game. Players Max and Min alternately place chips on the vertices of a graph. When a vertex accu…
Firefighting on square, hexagonal, and triangular grids
Tomas Gavenciak, Jan Kratochvil, Pawel Pralat
In this paper, we consider the \emph{firefighter problem} on a graph that is either finite or infinite. Suppose that a fire breaks out at a given vertex . In eac…
Almost all k-cop-win graphs contain a dominating set of cardinality k
Pawel Pralat
We consider -cop-win graphs in the binomial random graph It is known that almost all cop-win graphs contain a universal vertex. We generalize this result and prove t…
A note on the acquaintance time of random graphs
W. Kinnersley, D. Mitsche, P. Pralat
In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur on the acquaintance time of a random graph . It is shown that asymptotically almos…
Meyniel's conjecture holds for random graphs
Pawel Pralat, Nick Wormald
In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph is called the…