83 citations · 346 across the 78 of their papers we have counts for
11 papers · 1 filter
Meyniel's conjecture holds for random d-regular graphs
Pawel Pralat, Nicholas 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…
The Total Acquisition Number of the Randomly Weighted Path
Anant Godbole, Elizabeth Kelley, Emily Kurtz +2
There exists a significant body of work on determining the acquisition number of various graphs when the vertices of those graphs are each initially assigned a unit weight…
Non-Uniform Distribution of Nodes in the Spatial Preferential Attachment Model
Jeannette Janssen, Pawel Pralat, Rory Wilson
The spatial preferential attachment (SPA) is a model for complex networks. In the SPA model, nodes are embedded in a metric space, and each node has a sphere of influence whose siz…
Burning graphs - a probabilistic perspective
Dieter Mitsche, Pawel Pralat, Elham Roshanbin
In this paper, we study a graph parameter that was recently introduced, the burning number, focusing on a few probabilistic aspects of the problem. The original burning number is r…
Containment game played on random graphs: another zig-zag theorem
Pawel Pralat
We consider a variant of the game of Cops and Robbers, called Containment, in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but canno…
A probabilistic version of the game of Zombies and Survivors on graphs
Anthony Bonato, Dieter Mitsche, Xavier Pérez-Giménez +1
We consider a new probabilistic graph searching game played on graphs, inspired by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of zombies attempts to eat…
Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
Dieter Mitsche, Xavier Pérez-Giménez, Paweł Prałat
Consider the following model of strong-majority bootstrap percolation on a graph. Let r be some positive integer, and p in [0,1]. Initially, every vertex is active with probability…
Almost all 5-regular graphs have a 3-flow
Pawel Pralat, Nick Wormald
Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge-conne…
The set chromatic number of random graphs
Andrzej Dudek, Dieter Mitsche, Paweł Prałat
In this paper we study the set chromatic number of a random graph for a wide range of . We show that the set chromatic number, as a function of , forms an intri…
The bondage number of random graphs
Dieter Mitsche, Xavier Pérez-Giménez, Pawel Prałat
A dominating set of a graph is a subset of its vertices such that every vertex not in is adjacent to at least one member of . The domination number of a graph is the…
On-line list colouring of random graphs
Alan Frieze, Dieter Mitsche, Xavier Pérez-Giménez +1
In this paper, the on-line list colouring of binomial random graphs G(n,p) is studied. We show that the on-line choice number of G(n,p) is asymptotically almost surely asymptotic t…