83 citations · 346 across the 78 of their papers we have counts for
12 papers · 1 filter
The domination number of on-line social networks and random geometric graphs
Anthony Bonato, Marc Lozier, Dieter Mitsche +2
We consider the domination number for on-line social networks, both in a stochastic network model, and for real-world, networked data. Asymptotic sublinear bounds are rigorously de…
Game Brush Number
William B. Kinnersley, Pawel Pralat
We study a two-person game based on the well-studied brushing process on graphs. Players Min and Max alternately place brushes on the vertices of a graph. When a vertex accumulates…
Rainbow arborescence in random digraphs
Deepak Bal, Patrick Bennett, Colin Cooper +2
We consider the Erdős-Rényi random directed graph process, which is a stochastic process that starts with vertices and no edges, and at each step adds one new directed edge cho…
Power of choices and rainbow spanning trees in random graphs
Deepak Bal, Patrick Bennett, Alan Frieze +1
We consider the Erdős-Rényi random graph process, which is a stochastic process that starts with vertices and no edges, and at each step adds one new edge chosen uniformly at r…
An alternative proof of the linearity of the size-Ramsey number of paths
Andrzej Dudek, Pawel Pralat
The size Ramsey number of a graph is the smallest integer such that there exists a graph on edges with the property that any colouring of the edges of…
To catch a falling robber
William B. Kinnersley, Paweł Prałat, Douglas B. West
We consider a Cops-and-Robber game played on the subsets of an -set. The robber starts at the full set; the cops start at the empty set. On each turn, the robber moves down one…
Acquaintance time of random graphs near connectivity threshold
Andrzej Dudek, Paweł Prałat
Benjamini, Shinkar, and Tsur stated the following conjecture on the acquaintance time: asymptotically almost surely for a random graph $G \in G(n,p…
Dimensionality of social networks using motifs and eigenvalues
Anthony Bonato, David F. Gleich, Myunghwan Kim +4
We consider the dimensionality of social networks, and develop experiments aimed at predicting that dimension. We find that a social network model with nodes and links sampled from…
The Role of Visibility in Pursuit / Evasion Games
Athanasios Kehagias, Dieter Mitsche, Pawel Pralat
The cops-and-robber (CR) game has been used in mobile robotics as a discretized model (played on a graph G) of pursuit/evasion problems. The "classic" CR version is a perfect infor…
The Total Acquisition Number of Random Graphs
Deepak Bal, Patrick Bennett, Andrzej Dudek +1
Let be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex can be moved to a neighbouring vertex , provided that the weight on $v…
On the hyperbolicity of random graphs
Dieter Mitche, Pawel Pralat
Let be a connected graph with the usual (graph) distance metric . Introduced by Gromov, is -hyperbolic if for every four vertices $…
Chasing robbers on random geometric graphs---an alternative approach
Noga Alon, Pawel Pralat
We study the vertex pursuit game of \emph{Cops and Robbers}, in which cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a giv…