𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a method for random graphs

✍ Scribed by Zbigniew Palka; Andrzej Rucinśki; Joel Spencer

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
293 KB
Volume
61
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we examine a method for establishing an almost sure existence of a subgraph of a random graph with a given subgraph property. Since the method has been abused in the literature, we state some conditions under which it can be safely used. As an illustration we apply the method to induced cycles, maximal induced trees and arbitrary subgraphs of a random graph K,,.p.

📜 SIMILAR VOLUMES

Random walks on random simple graphs
Random walks on random simple graphs
✍ Martin Hildebrand 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 676 KB

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (logn)", where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou

On k-connectivity for a geometric random
On k-connectivity for a geometric random graph
✍ Mathew D. Penrose 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB 👁 1 views

For n points uniformly randomly distributed on the unit cube in d dimensions, ## Ž . with dG 2, let respectively, denote the minimum r at which the graph, obtained by n n adding an edge between each pair of points distant at most r apart, is k-connected Ž . w x respectively, has minimum degree k

On triangle-free random graphs
On triangle-free random graphs
✍ Tomasz Łuczak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 3 views

We show that for every k ≥ 1 and δ > 0 there exists a constant c > 0 such that, with probability tending to 1 as n → ∞, a graph chosen uniformly at random among all triangle-free graphs with n vertices and M ≥ cn 3/2 edges can be made bipartite by deleting δM edges. As an immediate consequence of th

General Partitioning on Random Graphs
General Partitioning on Random Graphs
✍ C.R. Subramanian; C.E. Veni Madhavan 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 158 KB

Consider the general partitioning (GP) problem defined as follows: Partition the vertices of a graph into k parts W 1 W k satisfying a polynomial time verifiable property. In particular, consider properties (introduced by T. Feder, P. Hell, S. Klein, and R. Motwani, in "Proceedings of the Annual ACM

Expected hitting times for a random walk
Expected hitting times for a random walk on a connected graph
✍ Gregory F Lawler 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 297 KB

A random walk on a graph is defined in which a particle moves from one vertex to any adjoining vertex, each with equal probability. The expected number of steps to get from one point to another is considered. It is shown that the maximum expectation for a graph with N vertices is O(N3). It is also s