Search

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree. [ABSTRACT FROM AUTHOR]

We propose the following extension of Dirac's theorem: if G $G$ is a graph with n≥3 $n\ge 3$ vertices and minimum degree δ(G)≥n∕2 $\delta (G)\ge n\unicode{x02215}2$, then in every orientation of G $G$ there is a Hamilton cycle with at least δ(G) $\delta (G)$ edges oriented in the same direction. We prove an approximate version of this conjecture, showing that minimum degree n+8k2 $\frac{n+8k}{2}$ guarantees a Hamilton cycle with at least (n+k)∕2 $(n+k)\unicode{x02215}2$ edges oriented in the same direction. We also study the analogous problem for random graphs, showing that if the edge probability p=p(n) $p=p(n)$ is above the Hamiltonicity threshold, then, with high probability, in every orientation of G~G(n,p) $G\unicode{x0007E}G(n,p)$ there is a Hamilton cycle with (1−o(1))n $(1-o(1))n$ edges oriented in the same direction. [ABSTRACT FROM AUTHOR]

We prove that a random graph G(n,p), with p above the Hamiltonicity threshold, is typically such that for any r‐coloring of its edges there exists a Hamilton cycle with at least (2/(r+1)−o(1))n edges of the same color. This estimate is asymptotically optimal. [ABSTRACT FROM AUTHOR]

We study graph-theoretic properties of the trace of a random walk on a random graph. We show that for any ε > 0 there exists C > 1 such that the trace of the simple random walk of length (1 + ε)n ln n on the random graph G~G(n, p) for p > C ln n/n is, with high probability, Hamiltonian and Θ(ln n)-connected. In the special case p = 1 (that is, when G = Kn), we show a hitting time result according to which, with high probability, exactly one step after the last vertex has been visited, the trace becomes Hamiltonian, and one step after the last vertex has been visited for the k'th time, the trace becomes 2k-connected. [ABSTRACT FROM AUTHOR]