86 citations · 344 across the 93 of their papers we have counts for
13 papers · 1 filter
Traveling in randomly embedded random graphs
Alan Frieze, Wesley Pegden
We consider the problem of traveling among random points in Euclidean space, when only a random fraction of the pairs are joined by traversable connections. In particular, we show…
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…
Looking for vertex number one
Alan Frieze, Wesley Pegden
Given an instance of the preferential attachment graph , we would like to find vertex 1, using only 'local' information about the graph; that is, by exploring the ne…
Cover time of a random graph with a degree sequence II: Allowing vertices of degree two
Colin Cooper, Alan Frieze, Eyal Lubetzky
We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set and degree sequence . In a previous work…
On random k-out sub-graphs of large graphs
Alan Frieze, Tony Johansson
We consider random sub-graphs of a fixed graph with large minimum degree. We fix a positive integer and let be the random sub-graph where each independ…
A note on the vacant set of random walks on the hypercube and other regular graphs of high degree
Colin Cooper, Alan Frieze
We consider a random walk on a -regular graph where and satisfies certain conditions. Our prime example is the -dimensional hypercube, which has …
Between 2- and 3-colorability
Alan Frieze, Wesley Pegden
We consider the question of the existence of homomorphisms between and odd cycles when . We show that for any positive integer , there exists $ε=…
Vacant sets and vacant nets: Component structures induced by a random walk
Colin Cooper, Alan Frieze
Given a discrete random walk on a finite graph , the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given st…
Elegantly colored paths and cycles in edge colored random graphs
Lisa Espig, Alan Frieze, Michael Krivelevich
We first consider the following problem. We are given a fixed perfect matching of and we add random edges one at a time until there is a Hamilton cycle containing . We…
Long paths in random Apollonian networks
Colin Cooper, Alan Frieze
We consider the length of the longest path in a randomly generated Apollonian Network (ApN) . We show that w.h.p. for any constant $c<2/…
The topology of competitively constructed graphs
Alan Frieze, Wesley Pegden
We consider a simple game, the -regular graph game, in which players take turns adding edges to an initially empty graph subject to the constraint that the degrees of vertices c…
Walker-Breaker games
Lisa Espig, Alan Frieze, Wesley Pegden +1
We introduce and analyze the Walker-Breaker game, a variant of Maker-Breaker games where Maker is constrained to choose edges of a walk or path in a given graph G, with the goal of…