✦ LIBER ✦

k-connectivity in random undirected graphs

✍ Scribed by John H Reif; Paul G Spirakis

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 591 KB
Volume: 54
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90079-2

No coin nor oath required. For personal study only.

✦ Synopsis

This paper concerns vertex connectivity in random graphs. We present results bounding the cardinality of the biggest k-block in random graphs of the G,~p model, for any constant value of k. Our results extend the work of Erd6s and R6nyi and Karp and Tarjan. We prove here that (~.~p, with [9 ~ tin, has a giant k-block almost surely, for any constant k > 0. The distribution of the size of the giant k-block is examined. We provide bounds on this distribution which are very nearly tight. We furthermore prove here that the cardinality of the biggest k-block is greater than n-log n, with probability at least 1-1/(n2]og rt), for p~c/n and c>k + 3. and NSF-MCS 83-00630 and the Office of Naval Research Contract N00014-80-C-0674.

📜 SIMILAR VOLUMES

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

A note on k-strongly connected orientati

A note on k-strongly connected orientations of an undirected graph

✍ András Frank 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 168 KB

Each k-strongly connected orientation of an undirect:7d I.&P A \_an be obtained from any other k-strongly connected orientation by reversing consec aLir :!I 3irected paths or circuits without destroying the k-strong connectivity.

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 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 (

Connectivity keeping paths in k-connecte

Connectivity keeping paths in k-connected graphs

✍ W. Mader 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 1 views

## Abstract A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph __G__ of minimum degree at least ⌊3__k__/2⌋ contains a vertex __x__ such that __G__−__x__ is still __k__‐connected. We generalize this result by proving t

Connectivity keeping trees in k-connecte

Connectivity keeping trees in k-connected graphs

✍ W. Mader 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

We show that one can choose the minimum degree of a k-connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G -V (T ) remains k-connected.