✦ LIBER ✦

Asymptotic estimates of the degree of connectivity of a random graph

✍ Scribed by Yu. D. Burtin

Publisher: Springer US
Year: 1975
Tongue: English
Weight: 374 KB
Volume: 9
Category: Article
ISSN: 1573-8337
DOI: 10.1007/bf01069208

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Local connectivity of a random graph

✍ P. Erdös; E. M. Palmer; R. W. Robinson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

## Abstract A graph is locally connected if for each vertex ν of degree __≧2__, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order __n_

On the existence of a factor of degree o

On the existence of a factor of degree one of a connected random graph

✍ P. Erdős; A. Rényi 📂 Article 📅 1966 🏛 Akadmiai Kiad 🌐 English ⚖ 432 KB

On k-leaf connectivity of a random graph

✍ Thomasz Luczak 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > f . A threshold function for k-leaf connectivity is also found. ## 1. MAIN RESULTS Let G = (V(G),E(G)) be a graph, where V (

The asymptotic behaviour of Fiedler's al

The asymptotic behaviour of Fiedler's algebraic connectivity for random graphs

✍ Ferenc Juhász 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 210 KB

The distribution of the maximum degree o

The distribution of the maximum degree of a random graph

✍ Béla Bollobás 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 184 KB

Consider I:andom graphs with n labelled vertices in which the edges are chosen independently and with a 6lxed probability p, 0 <p C 1. Let y be a fixed real number, q = 1p, and denote by A the maximum degree. Then

The vertex connectivity of a {0, 2}-grap

The vertex connectivity of a {0, 2}-graph equals its degree

✍ A.E. Brouwer; H.M. Mulder 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 140 KB

The first author observed that nice graphs are regular and have vertex connectivity equal to the degree. The second author observed that {0,2}-graphs are nice. This note follows immediately. A {0, 2}-graph is a connected graph such that any two distinct vertices have either 0 or 2 common neighbours