{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:25:17Z","timestamp":1759335917184},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2012,7,30]],"date-time":"2012-07-30T00:00:00Z","timestamp":1343606400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2012,11]]},"abstract":"<jats:p>A class<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>of labelled graphs is<jats:italic>bridge-addable<\/jats:italic>if, for all graphs<jats:italic>G<\/jats:italic>in<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>and all vertices<jats:italic>u<\/jats:italic>and<jats:italic>v<\/jats:italic>in distinct connected components of<jats:italic>G<\/jats:italic>, the graph obtained by adding an edge between<jats:italic>u<\/jats:italic>and<jats:italic>v<\/jats:italic>is also in<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>; the class<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>is<jats:italic>monotone<\/jats:italic>if, for all<jats:italic>G<\/jats:italic>\u2208<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>and all subgraphs<jats:italic>H<\/jats:italic>of<jats:italic>G<\/jats:italic>, we have<jats:italic>H<\/jats:italic>\u2208<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>. We show that for any bridge-addable, monotone class<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>whose elements have vertex set {1,.\u00a0.\u00a0.,<jats:italic>n<\/jats:italic>}, the probability that a graph chosen uniformly at random from<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000272_char1\" \/><\/jats:private-char>is connected is at least (1\u2212<jats:italic>o<jats:sub>n<\/jats:sub><\/jats:italic>(1))<jats:italic>e<\/jats:italic><jats:sup>\u2212\u00bd<\/jats:sup>, where<jats:italic>o<jats:sub>n<\/jats:sub><\/jats:italic>(1) \u2192 0 as<jats:italic>n<\/jats:italic>\u2192 \u221e. This establishes the special case of the conjecture of McDiarmid, Steger and Welsh when the condition of monotonicity is added. This result has also been obtained independently by Kang and Panagiotou.<\/jats:p>","DOI":"10.1017\/s0963548312000272","type":"journal-article","created":{"date-parts":[[2012,7,30]],"date-time":"2012-07-30T08:51:44Z","timestamp":1343638304000},"page":"803-815","source":"Crossref","is-referenced-by-count":10,"title":["Connectivity for Bridge-Addable Monotone Graph Classes"],"prefix":"10.1017","volume":"21","author":[{"given":"L.","family":"ADDARIO-BERRY","sequence":"first","affiliation":[]},{"given":"C.","family":"MCDIARMID","sequence":"additional","affiliation":[]},{"given":"B.","family":"REED","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2012,7,30]]},"reference":[{"key":"S0963548312000272_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.007"},{"key":"S0963548312000272_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325975.008"},{"key":"S0963548312000272_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00624-3"},{"key":"S0963548312000272_ref11","doi-asserted-by":"crossref","first-page":"R114","DOI":"10.37236\/838","article-title":"The number of graphs not containing K3,3 as a minor","volume":"15","author":"Gerke","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548312000272_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.03.001"},{"key":"S0963548312000272_ref19","first-page":"73","article-title":"Some remarks on the theory of trees","volume":"4","author":"R\u00e9nyi","year":"1959","journal-title":"Publ. Math. Inst. Hungarian Acad. Sci."},{"key":"S0963548312000272_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2010.11.014"},{"key":"S0963548312000272_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000532"},{"key":"S0963548312000272_ref8","first-page":"376","article-title":"A theorem on trees","volume":"23","author":"Cayley","year":"1889","journal-title":"Quart. J. Math."},{"key":"S0963548312000272_ref18","volume-title":"Counting Labelled Trees","author":"Moon","year":"1970"},{"key":"S0963548312000272_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2007.07.080"},{"key":"S0963548312000272_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548312000272_ref5","doi-asserted-by":"crossref","unstructured":"Bodirsky M. , Gim\u00e9nez O. , Kang M. and Noy M. (2005) On the number of series parallel and outerplanar graphs. In Proc. European Conference on Combinatorics, Graph Theory, and Applications: EuroComb '05, DMTCS Proceedings Series, pp. 383\u2013388.","DOI":"10.46298\/dmtcs.3451"},{"key":"S0963548312000272_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.09.003"},{"key":"S0963548312000272_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33700-8_15"},{"key":"S0963548312000272_ref20","volume-title":"Introduction to Graph Theory","author":"West","year":"2001"},{"key":"S0963548312000272_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.011"},{"key":"S0963548312000272_ref3","doi-asserted-by":"crossref","first-page":"P13","DOI":"10.37236\/500","article-title":"Asymptotic enumeration of labelled graphs by genus","volume":"18","author":"Bender","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S0963548312000272_ref2","unstructured":"Balister P. , Bollob\u00e1s B. and Gerke S. (2010) Connectivity of random addable graphs. In Proc. ICDM 2008, Vol. 13, pp. 127\u2013134."},{"key":"S0963548312000272_ref15","doi-asserted-by":"crossref","unstructured":"Kang M. and Panagiotou K. (2012) On the connectivity of random graphs from addable classes. Submitted.","DOI":"10.1016\/j.jctb.2012.12.001"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000272","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T21:07:03Z","timestamp":1643058423000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000272\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,30]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["S0963548312000272"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000272","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7,30]]}}}