𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Resilient Pancyclicity of Random and Pseudorandom Graphs

✍ Scribed by Krivelevich, Michael; Lee, Choongbum; Sudakov, Benny

Book ID
118197822
Publisher
Society for Industrial and Applied Mathematics
Year
2010
Tongue
English
Weight
260 KB
Volume
24
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Pancyclic subgraphs of random graphs
Pancyclic subgraphs of random graphs
✍ Choongbum Lee; Wojciech Samotij πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## 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 f

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

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