Recognition: unknown
Long cycles in subgraphs of (pseudo)random directed graphs
classification
🧮 math.CO
keywords
directedgammarandomcyclecyclesedgesgraphsleast
read the original 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'$ be a subgraph of $G$ with $(1/2+\gamma)|E|$ edges. Then $G'$ contains a directed cycle of length at least $(c-o(1))n$. Moreover, there is a subgraph $G''$ of $G$ with $(1/2+\gamma-o(1))|E|$ edges that does not contain a cycle of length at least $cn$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.