𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Spanning subgraphs of random graphs

✍ Scribed by Noga Alon; Zoltán Füredi

Publisher
Springer Japan
Year
1992
Tongue
English
Weight
183 KB
Volume
8
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The spanning subgraphs of eulerian graph
The spanning subgraphs of eulerian graphs
✍ F. T. Boesch; C. Suffel; R. Tindell 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

## Abstract It is shown that a connected graph __G__ spans an eulerian graph if and only if __G__ is not spanned by an odd complete bigraph __K__(2~m~ + 1, 2__n__ + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd

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

Extremal subgraphs of random graphs
Extremal subgraphs of random graphs
✍ László Babai; Miklós Simonovits; Joel Spencer 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 1015 KB

## Abstract We shall prove that if __L__ is a 3‐chromatic (so called “forbidden”) graph, and —__R__^__n__^ is a random graph on __n__ vertices, whose edges are chosen independently, with probability __p__, and —__B__^__n__^ is a bipartite subgraph of __R__^__n__^ of maximum size, —__F__^__n__^ is a

Spanning even subgraphs of 3-edge-connec
Spanning even subgraphs of 3-edge-connected graphs
✍ Bill Jackson; Kiyoshi Yoshimoto 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec