2026-04-17T02:51:07Zhttps://recercat.cat/oai/request

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

00925njm 22002777a 4500 dc Castellví, J. author Drmota, M. author Noy, M. author Requilé, C. author 2024-06-01 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. http://hdl.handle.net/2072/537574 10.1016/j.aam.2024.102700 Chordal graphs with bounded tree-width