{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:22:59Z","timestamp":1759335779621},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"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":[[2009,9]]},"abstract":"<jats:p>In this work we determine the expected number of vertices of degree<jats:italic>k<\/jats:italic>=<jats:italic>k<\/jats:italic>(<jats:italic>n<\/jats:italic>) in a graph with<jats:italic>n<\/jats:italic>vertices that is drawn uniformly at random from a<jats:italic>subcritical graph class<\/jats:italic>. Examples of such classes are outerplanar, series-parallel, cactus and clique graphs. Moreover, we provide exponentially small bounds for the probability that the quantities in question deviate from their expected values.<\/jats:p>","DOI":"10.1017\/s0963548309990368","type":"journal-article","created":{"date-parts":[[2009,8,20]],"date-time":"2009-08-20T10:38:15Z","timestamp":1250764695000},"page":"647-681","source":"Crossref","is-referenced-by-count":15,"title":["The Degree Sequence of Random Graphs from Subcritical Classes"],"prefix":"10.1017","volume":"18","author":[{"given":"NICLA","family":"BERNASCONI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KONSTANTINOS","family":"PANAGIOTOU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANGELIKA","family":"STEGER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,9,1]]},"reference":[{"key":"S0963548309990368_ref12","unstructured":"[12] Fusy \u00c9. (2005) Quadratic exact-size and linear approximate-size random generation of planar graphs. In 2005 International Conference on Analysis of Algorithms ( Mart\u00ednez C. , ed.), Vol. AD of DMTCS Proceedings, pp. 125\u2013138."},{"key":"S0963548309990368_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90226-7"},{"key":"S0963548309990368_ref20","unstructured":"[20] Weissl A. C. (2007) Random graphs with structural constraints. PhD Thesis."},{"key":"S0963548309990368_ref1","doi-asserted-by":"crossref","first-page":"#43","DOI":"10.37236\/1659","article-title":"The number of labeled 2-connected planar graphs","volume":"9","author":"Bender","year":"2002","journal-title":"Electron. J. Combin."},{"key":"S0963548309990368_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548309990368_ref2","volume-title":"Combinatorial Species and Tree-Like Structures","author":"Bergeron","year":"1998"},{"key":"S0963548309990368_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(82)90072-7"},{"key":"S0963548309990368_ref13","first-page":"999","volume-title":"Proc. 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"Gerke","year":"2005"},{"key":"S0963548309990368_ref7","first-page":"61","article-title":"The random planar graph.","volume":"113","author":"Denise","year":"1996","journal-title":"Congr. Numer."},{"key":"S0963548309990368_ref8","unstructured":"[8] Drmota M. , Gim\u00e9nez O. and Noy M. Vertices of given degree in series-parallel graphs. Random Structures and Algorithms. To appear."},{"key":"S0963548309990368_ref4","doi-asserted-by":"crossref","unstructured":"[4] Bodirsky M. , Gim\u00e9nez O. , Kang M. and Noy M. (2005) On the number of series parallel and outerplanar graphs. In 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb \u201905), Vol. AE of DMTCS Proceedings, pp. 383\u2013388.","DOI":"10.46298\/dmtcs.3451"},{"key":"S0963548309990368_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.007"},{"key":"S0963548309990368_ref3","unstructured":"[3] Bernasconi N. , Panagiotou K. and Steger A. (2008) On properties of random dissections and triangulations. In Proc. 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA \u201908), pp. 132\u2013141. Full version submitted Dec \u201907, available at: www.as.inf.ethz.ch\/research\/publications\/2008\/index\/."},{"key":"S0963548309990368_ref17","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1307\/mmj\/1029000098","article-title":"On the maximum degree in a random tree.","volume":"15","author":"Moon","year":"1968","journal-title":"Michigan Math. J."},{"key":"S0963548309990368_ref14","doi-asserted-by":"crossref","unstructured":"[14] Gim\u00e9nez O. and Noy M. (2005) The number of planar graphs and properties of random planar graphs. In 2005 International Conference on Analysis of Algorithms, Vol. AD of DMTCS Proceedings, pp. 147\u2013156.","DOI":"10.46298\/dmtcs.3354"},{"key":"S0963548309990368_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"S0963548309990368_ref6","doi-asserted-by":"crossref","first-page":"#148","DOI":"10.37236\/872","article-title":"A complete grammar for decomposing a family of graphs into 3-connected components","volume":"15","author":"Chapuy","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548309990368_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548309990368_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548309990368_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511805967"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T11:46:28Z","timestamp":1685101588000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990368\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["S0963548309990368"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990368","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]}}}