Chordal graphs with bounded tree-width

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.