Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the number of labeled graphs of bounded treewidth

Autor
Baste, J.; Noy, M.; Sau, I.
Tipus d'activitat
Article en revista
Revista
European journal of combinatorics
Data de publicació
2018-06-01
Volum
71
Pàgina inicial
12
Pàgina final
12
DOI
https://doi.org/10.1016/j.ejc.2018.02.030 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/115956 Obrir en finestra nova
https://arxiv.org/abs/1604.07273 Obrir en finestra nova
URL
https://link.springer.com/chapter/10.1007%2F978-3-319-68705-6_7 Obrir en finestra nova
Resum
Let be Tnk the number of labeled graphs on vertices and treewidth at most (equivalently, the number o1 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 lambda-trees, while the lower bound is obtained from an explicit construction. It follows from this constru...
Citació
Baste, J., Noy, M., Sau, I. On the number of labeled graphs of bounded treewidth. "European journal of combinatorics", 1 Juny 2018, vol. 71, p. 12.
Paraules clau
Enumeration, Partial K-trees, Pathwidth, Properpathwidth., Treewidth
Grup de recerca
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants