On the number of labeled graphs of bounded treewidth. (June 2018)

• Record Type: Journal Article
• Authors: Baste, Julien; Noy, Marc; Sau, Ignasi
• Is Part Of: European journal of combinatorics. Volume 71(2018)
• Page Start: 12
• Page End: 21
• Publication Date: 2018-06
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.02.030
• Languages: English
• ISSNs: 0195-6698

Abstract

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 .