Dellamonica, Domingos jun.; Kohayakawa, Yoshiharu; Marciniszyn, Martin; Steger, Angelika

On the resilience of long cycles in random graphs

Electron. J. Comb. 15(1), Research Paper R32, 26 p. (2008)

Summary

Summary: In this paper we determine the local and global resilience of random graphs Gn,p (p n - 1) with respect to the property of containing a cycle of length at least $(1 - \alpha )$n. Roughly speaking, given $\alpha > 0$, we determine the smallest $rg(G, \alpha )$ with the property that almost surely every subgraph of G = Gn,p having more than $rg(G, \alpha )|E(G)$| edges contains a cycle of length at least $(1 - \alpha )$n (global resilience). We also obtain, for $\alpha < 1/2$, the smallest $rl(G, \alpha )$ such that any H $\subseteq G$ having $degH(v)$ larger than $rl(G, \alpha ) degG(v)$ for all v $\in V$ (G) contains a cycle of length at least $(1 - \alpha )$n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

Mathematics Subject Classification

05C35, 05C38, 05C80

Downloads