On the number of labeled graphs of bounded treewidth

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/115956

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor	Universitat Politècnica de Catalunya. MD - Matemàtica Discreta
dc.contributor.author	Baste, Julien
dc.contributor.author	Noy Serrano, Marcos
dc.contributor.author	Sau, Ignasi
dc.date	2018-06-01
dc.identifier.citation	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.
dc.identifier.citation	0195-6698
dc.identifier.citation	https://arxiv.org/abs/1604.07273
dc.identifier.citation	10.1016/j.ejc.2018.02.030
dc.identifier.uri	http://hdl.handle.net/2117/115956
dc.language.iso	eng
dc.relation	https://link.springer.com/chapter/10.1007%2F978-3-319-68705-6_7
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	05C85
dc.subject	05C30
dc.title	On the number of labeled graphs of bounded treewidth
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/article
dc.description.abstract	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 construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most k .