2026-04-18T07:55:31Zhttps://recercat.cat/oai/request

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

Chordal graphs with bounded tree-width Castellví, J. Drmota, M. Noy, M. Requilé, C. Chordal Graphs, Bounded tree-width 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. The authors acknowledge support from the Marie Curie RISE research network “RandNet” MSCA-RISE-2020-101007705. Moreover, M.D. was supported by the Special Research Program SFB F50-02 “Algorithmic and Enumerative Combinatorics”, and by the project P35016 “Infinite Singular Systems and Random Discrete Objects” of the FWF (Austrian Science Fund). Additionally, M.N. and C.R. acknowledge the financial support of the Spanish State Research Agency through projects MTM2017-82166-P and PID2020-113082GB-I00, while M.N. acknowledges support from the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence (CEX2020-001084-M), and C.R. acknowledges support from the grant Beatriu de Pinós BP2019, funded by the H2020 COFUND project No 801370 and AGAUR (the Catalan agency for management of university and research grants). 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 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/ info:eu-repo/semantics/openAccess 23 p. application/pdf Academic Press Inc. RECERCAT (Dipòsit de la Recerca de Catalunya)