✦ LIBER ✦

On k-leaf connectivity of a random graph

✍ Scribed by Thomasz Luczak

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 367 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120102

No coin nor oath required. For personal study only.

✦ Synopsis

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 ( G ) is its vertex set and E ( G ) denotes its set of edges. A graph G is k-leaf connected for some natural number k 2 2 if for every subset S C V ( G ) , IS1 = k , there exists a spanning tree of G such that S is the set of its endpoints. This concept was introduced by Murty as a generalization of hamiltonian connectivity (for recent results see [ 5 ] ) . Notice that 2-leaf connectivity is equivalent to the notion of hamiltonian connectivity, i.e., that every pair of vertices is joined by a hamiltonian path. Now let Kn,N denote a random graph with n vertices and N edges, where each of the ('2) possible graphs is equally likely.

We shall prove the following result:

The 2-leaf connectedness property (i.e., hamiltonian connectivity) of a random graph been considered by Bollobas [2], and recently by Bollobas. Fenner and Frieze [3], who proved Theorem 1 for the case k = 2 using an algorithmic approach.

📜 SIMILAR VOLUMES

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

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_

The Connectivities of Leaf Graphs of 2-C

The Connectivities of Leaf Graphs of 2-Connected Graphs

✍ Atsushi Kaneko; Kiyoshi Yoshimoto 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 286 KB

Given a connected graph G, denote by V the family of all the spanning trees of G. Define an adjacency relation in V as follows: the spanning trees t and t$ are said to be adjacent if for some vertex u # V, t&u is connected and coincides with t$&u. The resultant graph G is called the leaf graph of G.

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

On the edge-connectivity vector of a gra

On the edge-connectivity vector of a graph

✍ Linda M. Lesniak; Raymond E. Pippert 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

On k-con-Critically n-Connected Graphs

✍ W. Mader 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 221 KB

We prove that every n-connected graph G of sufficiently large order contains a connected graph H on four vertices such that G À V ðH Þ is ðn À 3Þ-connected. This had been conjectured in Mader (High connectivity keeping sets in n-connected graphs, Combinatorica, to appear). Furthermore, we prove uppe