Premium
Connectivity properties of random subgraphs of the cube
Author(s) -
Bollobás B.,
Kohayakawa Y.,
Luczak T.
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060210
Subject(s) - combinatorics , mathematics , vertex (graph theory) , social connectedness , graph , disjoint sets , random graph , discrete mathematics , psychology , psychotherapist
The n ‐dimensional cube Q n is the graph whose vertices are the subsets of {1, n } where two such vertices are adjacent if and only if their symmetric difference is a singleton. Clearly Q n is an n‐connected graph of diameter and radius n. Write M = n2n −1 = e(Q n ) for the size of Q n . Let Q̃ = (Q t ) M 0 be a random Q̃ ‐process. Thus Q t is a spanning subgraph of Q n of size t , and Q t is obtained from Q t‐1 by the random addition of an edge of Q n not in Q t‐1 . Let t (k) = τ(Q̃ δ ≧ k) be the hitting time of the property of having minimal degree at least k. It is shown in [5] that, almost surely, at time t (1) the graph Q t becomes connected and that in fact the diameter of Q t at this point is n + 1. Here we generalize this result by showing that, for any fixed k≧2 , almost surely at time t (k) the graph Q t acquires the extremely strong property that any two of its vertices are connected by k internally vertex‐disjoint paths each of length at most n , except for possibly one, which may have length n + 1. In particular, the hitting time of k ‐connectedness is almost surely t (k) . © 1995 John Wiley & Sons, Inc.