Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903572 | European Journal of Combinatorics | 2018 | 10 Pages |
Abstract
Let Tn,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 ck2knlogkn2âk(k+3)2kâ2kâ2â¤Tn,kâ¤k2knn2âk(k+1)2kâ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 (logk)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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Julien Baste, Marc Noy, Ignasi Sau,