Sets that are connected in two random graphs. Issue 3 (13th March 2013)

• Record Type: Journal Article
• Authors: Molloy, Michael
• Is Part Of: Random structures & algorithms. Volume 45:Issue 3(2014)
• Page Start: 498
• Page End: 512
• Publication Date: 2013-03-13
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20491
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>–We consider two random graphs <italic>G</italic>₁, <italic>G</italic>₂, both on the same vertex set. We ask whether there is a non‐trivial set of vertices <italic>S</italic>, so that <italic>S</italic> induces a connected subgraph both in <italic>G</italic>₁ and in <italic>G</italic>₂. We determine the threshold for the appearance of such a subset, as well as the size of the largest such subset. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 498–512, 2014</p> </abstract>