{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:46:40Z","timestamp":1773820000755,"version":"3.50.1"},"reference-count":11,"publisher":"Wiley","issue":"2-3","license":[{"start":{"date-parts":[[2007,7,5]],"date-time":"2007-07-05T00:00:00Z","timestamp":1183593600000},"content-version":"vor","delay-in-days":4509,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1995,3]]},"abstract":"Abstract<\/jats:title>The n<\/jats:italic>\u2010dimensional cube Qn<\/jats:sup><\/jats:italic> is the graph whose vertices are the subsets of {1, n<\/jats:italic>} where two such vertices are adjacent if and only if their symmetric difference is a singleton. Clearly Qn<\/jats:sup><\/jats:italic> is an n\u2010connected graph of diameter and radius n.<\/jats:italic> Write M = n2n\u22121<\/jats:sup> = e(Qn<\/jats:sup>)<\/jats:italic> for the size of Qn<\/jats:sup>.<\/jats:italic> Let Q\u0303 = (Qt<\/jats:sub>)M<\/jats:sup>0<\/jats:sub><\/jats:italic> be a random Q\u0303<\/jats:italic>\u2010process. Thus Qt<\/jats:sub><\/jats:italic> is a spanning subgraph of Qn<\/jats:sup><\/jats:italic> of size t<\/jats:italic>, and Qt<\/jats:sub><\/jats:italic> is obtained from Qt\u20101<\/jats:sub> by the random addition of an edge of Qn<\/jats:sup><\/jats:italic> not in Qt\u20101<\/jats:sub><\/jats:italic>. Let t(k)<\/jats:sup> = \u03c4(Q\u0303 \u03b4<\/jats:italic> \u2267 k)<\/jats:italic> be the hitting time of the property of having minimal degree at least k.<\/jats:italic> It is shown in [5] that, almost surely, at time t(1)<\/jats:sup><\/jats:italic> the graph Qt<\/jats:sub><\/jats:italic> becomes connected and that in fact the diameter of Qt<\/jats:sub><\/jats:italic> at this point is n +<\/jats:italic> 1. Here we generalize this result by showing that, for any fixed k\u22672<\/jats:italic>, almost surely at time t(k)<\/jats:sup><\/jats:italic> the graph Qt<\/jats:sub><\/jats:italic> acquires the extremely strong property that any two of its vertices are connected by k<\/jats:italic> internally vertex\u2010disjoint paths each of length at most n<\/jats:italic>, except for possibly one, which may have length n +<\/jats:italic> 1. In particular, the hitting time of k<\/jats:italic>\u2010connectedness is almost surely t(k)<\/jats:sup>.<\/jats:italic> \u00a9 1995 John Wiley & Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240060210","type":"journal-article","created":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T01:53:44Z","timestamp":1278899624000},"page":"221-230","source":"Crossref","is-referenced-by-count":7,"title":["Connectivity properties of random subgraphs of the cube"],"prefix":"10.1002","volume":"6","author":[{"given":"B.","family":"Bollob\u00e1s","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Kohayakawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Luczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,7,5]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579276"},{"key":"e_1_2_1_2_2","first-page":"xvi","volume-title":"Random Graphs","author":"Bollob\u00b4s B.","year":"1985"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010107"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030106"},{"key":"e_1_2_1_5_2","article-title":"On the diameter and radius of random subgraphs of the cube","author":"Bollob\u00e1s B.","journal-title":"Random Struct. Alg."},{"key":"e_1_2_1_6_2","first-page":"47","volume-title":"Random Graphs '83, Annals of Discrete Mathematics 28","author":"Bollob\u00e1s B.","year":"1985"},{"key":"e_1_2_1_7_2","first-page":"17","volume-title":"Random Graphs '85, Annals of Discrete Mathematics 33","author":"Dyer M. E.","year":"1987"},{"key":"e_1_2_1_8_2","first-page":"125","volume-title":"Combinatorics, Paul Erd\u00f6s Is Eighty","author":"Faudree R. J.","year":"1993"},{"key":"e_1_2_1_9_2","first-page":"155","volume-title":"Annals of Discrete Mathematics 51","author":"Kostochka A. V.","year":"1992"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040207"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02019432"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240060210","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240060210","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240060210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T04:08:57Z","timestamp":1693454937000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240060210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":11,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["10.1002\/rsa.3240060210"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240060210","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}