✦ LIBER ✦

Local connectivity of a random graph

✍ Scribed by P. Erdös; E. M. Palmer; R. W. Robinson

Publisher: John Wiley and Sons
Year: 1983
Tongue: English
Weight: 255 KB
Volume: 7
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190070405

No coin nor oath required. For personal study only.

✦ Synopsis

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 is p = ((3/2 +ϵ~n~) log n/n)^1/2^ where ϵ~n~ = (log log n + log(3/8) + 2x)/(2 log n), then the limiting probability that a random graph is locally connected is exp(‐exp(‐x)).

📜 SIMILAR VOLUMES

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 (

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

Quantum Simulations of Classical Random

Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity

✍ John Watrous 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 160 KB

While it is straightforward to simulate a very general class of random processes space-efficiently by non-unitary quantum computations (e.g., quantum computations that allow intermediate measurements to occur), it is not currently known to what extent restricting quantum computations to be unitary a

Every connected, locally connected graph

Every connected, locally connected graph is upper embeddable

✍ Ladislav Nebeský 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract In this Note it is proved that every connected, locally connected graph is upper embeddable. Moreover, a lower bound for the maximum genus of the square of a connected graph is given.

The rainbow connectivity of a graph

✍ Gary Chartrand; Garry L. Johns; Kathleen A. McKeon; Ping Zhang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

A local structure theorem on 5-connected

A local structure theorem on 5-connected graphs

✍ Kiyoshi Ando 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 281 KB

## Abstract An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let __x__ be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from __x__ is two or less, then either there are two tri