On the number of labeled graphs of bounded treewidth. (June 2018) - Baste, Julien; Noy, Marc; Sau, Ignasi
Abstract: Let T n, k be the number of labeled graphs on n vertices and treewidth at most k (equivalently, the number of labeled partial k -trees). We show that c k 2 k n log k n 2 − k ( k + 3 ) 2 k − 2 k − 2 ≤ T n, k ≤ k 2 k n n 2 − k ( k + 1 ) 2 k − k, for k > 1 and some explicit absolute constant c > 0 . Disregarding terms depending only on k, the gap between the lower and upper bound is of order ( log k ) n . The upper bound is a direct consequence of the well-known formula for the number of labeled k -trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most k .