Long cycles in subgraphs of (pseudo)random directed graphs

Abstract

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every $0<\gamma <1/2$ we find a constant $c=c(\gamma )$ such that the following holds. Let $G=(V,E)$ be a (pseudo)random directed graph on $n$ vertices, and let $G^{\prime }$ be a subgraph of $G$ with $(1/2+\gamma )|E|$ edges. Then $G^{\prime }$ contains a directed cycle of length at least $(c-o(1))n$. Moreover, there is a subgraph $G^{\prime \prime }$ of $G$ with $(1/2+\gamma -o(1))|E|$ edges that does not contain a cycle of length at least $cn$.

References in corpus (1)

• Increasing the chromatic number of a random graph

Cited by in corpus (1)

• Longest cycles in sparse random digraphs