The Largest Component In A Random Subgraph Of The N-Cycle

TitleThe Largest Component In A Random Subgraph Of The N-Cycle
Publication TypeConference Paper
AuthorsKatona, G. O. H., and L. V. Quintas
Year1993
Pages113 - 116
Conference NameDiscrete Mathematics
Languageeng
ISBN Number0012-365x
Notes

exported from refbase (http://www.bibliography.ceu.hu/show.php?record=6261), last updated on Mon, 02 Nov 2009 10:38:10 +0100

Abstract

Let M denote the order of the largest component in a random subgraph H of the n-cycle C(n), where H has the same vertex set as C(n) and its edge set is defined by independently selecting, with the same constant probability, each of the edges of C(n). The probability that M is equal to k is known for k = 1 and for n greater-than-or-equal-to k greater-than-or-equal-to [n/2]. Here we obtain the exact result for k = 2 and comment on the cases [n/2]>k>2.