2026-04-13T13:27:07Zhttps://recercat.cat/oai/request

oai:recercat.cat:2072/5375742024-12-20T01:43:17Zcom_2072_199267com_2072_4427col_2072_201036

2024-05-06T11:22:07Z urn:hdl:2072/537574 Chordal graphs with bounded tree-width Castellví, J. Drmota, M. Noy, M. Requilé, C. Given t≥2 and 0≤k≤t, we prove that the number of labelled k-connected chordal graphs with n vertices and tree-width at most t is asymptotically cn−5/2γnn!, as n→∞, for some constants c,γ>0 depending on t and k. Additionally, we show that the number of i-cliques (2≤i≤t) in a uniform random k-connected chordal graph with tree-width at most t is normally distributed as n→∞. The asymptotic enumeration of graphs of tree-width at most t is wide open for t≥3. To the best of our knowledge, this is the first non-trivial class of graphs with bounded tree-width where the asymptotic counting problem is solved. Our starting point is the work of Wormald (1985) [21], were an algorithm is developed to obtain the exact number of labelled chordal graphs on n vertices. © 2024 Elsevier Inc. 2024-05-06T11:22:07Z 2024-09-19T14:25:53Z 2024-05-06T11:22:07Z 2024-09-19T14:25:53Z 2024-06-01 info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion http://hdl.handle.net/2072/537574 10.1016/j.aam.2024.102700 eng Advances in Applied Mathematics info:eu-repo/semantics/openAccess L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/ Academic Press Inc. RECERCAT (Dipòsit de la Recerca de Catalunya)