Castellví, J., Drmota, M., Noy, M., & Requilé, C. (2023). Chordal graphs with bounded tree-width. In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (pp. 270–276). https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-037
E104-05 - Forschungsbereich Kombinatorik und Algorithmen
-
Published in:
Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications
-
ISBN:
978-80-280-0344-9
-
Date (published):
19-Mar-2023
-
Event name:
EUROCOMB 23
en
Event date:
28-Aug-2023 - 1-Sep-2023
-
Event place:
Czechia
-
Number of Pages:
7
-
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 [Counting Labelled Chordal Graphs, Graphs and Combinatorics (1985)], 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)
