Long cycles in subgraphs of (pseudo)random directed graphs

2010/09/20 by Ido Ben‐Eliezer, Michael Krivelevich, Ben-Eliezer, Ido +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1009.3721

openalex publication_date 2010/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 0 < γ< 1/2 we find a constant c=c(γ) 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+γ)|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+γ-o(1))|E| edges that does not contain a cycle of length at least cn.

Citations

• Increasing the chromatic number of a random graph

Cited by

• Size-Ramsey numbers of tight paths

Related

• Resilient pancyclicity of random and pseudo-random graphs
• Turán-type problems for long cycles in random and pseudo-random graphs
• A large hole in pseudo-random graphs
• On the local resilience of random geometric graphs with respect to connectivity and long cycles
• Cycle lengths in sparse random graphs