Castellví, J., Drmota, M., Noy, M., & Requilé, C. (2024). Chordal graphs with bounded tree-width. Advances in Applied Mathematics, 157, Article 102700. https://doi.org/10.1016/j.aam.2024.102700
E104-05 - Forschungsbereich Kombinatorik und Algorithmen
-
Journal:
Advances in Applied Mathematics
-
ISSN:
0196-8858
-
Date (published):
2024
-
Publisher:
ACADEMIC PRESS INC ELSEVIER SCIENCE
-
Peer reviewed:
Yes
-
Keywords:
chordal graphs
en
Abstract:
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.
en
Project title:
Unendliche singuläre Systeme und zufällig diskrete Objekte: P 35016-N (FWF - Österr. Wissenschaftsfonds)