✦ LIBER ✦

Long cycles in subgraphs of (pseudo)random directed graphs

✍ Scribed by Ido Ben-Eliezer; Michael Krivelevich; Benny Sudakov

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 152 KB
Volume: 70
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20616

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/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 with at least a linear number of edges, 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. © 2011 Wiley Periodicals, Inc. J Graph Theory 70: 284–296, 2012

📜 SIMILAR VOLUMES

Hamilton cycles in random graphs and dir

Hamilton cycles in random graphs and directed graphs

✍ Colin Cooper; Alan Frieze 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 3 views

Hamilton Cycles in a Class of Random Dir

Hamilton Cycles in a Class of Random Directed Graphs

✍ C. Cooper; A. Frieze 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 449 KB

Compound Poisson approximations of subgr

Compound Poisson approximations of subgraph counts in random graphs

✍ Dudley Stark 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views

Long Cycles and 3-Connected Spanning Sub

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs

✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let \(G\) be a 3-connected \(K_{1, d}\)-free graph on \(n\) vertices. We show that \(G\) contains a 3-connected spanning subgraph of maximum degree at most \(2 d-1\). Using an earlier result of ours, we deduce that \(G\) contains a cycle of length at least \(\frac{1}{2} n^{c}\) where \(c=\left(\log

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for