𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Pancyclic subgraphs of random graphs

✍ Scribed by Choongbum Lee; Wojciech Samotij

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
249 KB
Volume
71
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An n‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≀t≀n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n^βˆ’1/2^, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). Β© 2011 Wiley Periodicals, Inc.

πŸ“œ SIMILAR VOLUMES

Pancyclicity of 3-connected graphs: Pair
Pancyclicity of 3-connected graphs: Pairs of forbidden subgraphs
✍ Ronald J. Gould; Tomasz Łuczak; Florian Pfender πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 232 KB

## Abstract We characterize all pairs of connected graphs {__X__, __Y__} such that each 3‐connected {__X__, __Y__}‐free graph is pancyclic. In particular, we show that if each of the graphs in such a pair {__X__, __Y__} has at least four vertices, then one of them is the claw __K__~1,3~, while the

Random Subgraphs of Cayley Graphs overp-
Random Subgraphs of Cayley Graphs overp-Groups
✍ C.M. Reidys πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 146 KB

The subject of this paper is the size of the largest component in random subgraphs of Cayley graphs, X n , taken over a class of p-groups, G n . G n consists of p-groups, G n , with the following properties: , where K is some positive constant. We consider Cayley graphs X n = (G n , S n ), where S

Long cycles in subgraphs of (pseudo)rand
Long cycles in subgraphs of (pseudo)random directed graphs
✍ Ido Ben-Eliezer; Michael Krivelevich; Benny Sudakov πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 152 KB

## 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__ vertice

Pancyclicity of connected circulant grap
Pancyclicity of connected circulant graphs
✍ Bogdanowicz, Z. R. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 299 KB πŸ‘ 1 views

The circulant G,(al,. . . , ak), where 0 < al < ... < a k < ( n + 1 ) / 2 , is defined as the vertex-transitive graph that has vertices ifal,. . . ,if a k (mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In additi