dc.contributor.author
Castellví, J.
dc.contributor.author
Noy, M.
dc.contributor.author
Requilé, C.
dc.date.accessioned
2023-05-25T13:20:28Z
dc.date.accessioned
2024-09-19T14:25:41Z
dc.date.available
2023-05-25T13:20:28Z
dc.date.available
2024-09-19T14:25:41Z
dc.date.issued
2022-09-22
dc.identifier.uri
http://hdl.handle.net/2072/534626
dc.description.abstract
We determine the number of labelled chordal planar graphs with n vertices, which is asymptotically g⋅n−5/2γnn! for a constant g>0 and γ≈11.89235. We also determine the number of rooted simple chordal planar maps with n edges, which is asymptotically s⋅n−3/2δn, where s>0, δ=1/σ≈6.40375, and σ is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from K4 by repeatedly adding vertices adjacent to an existing triangular face. © 2022 The Author(s)
eng
dc.description.sponsorship
We gratefully acknowledge earlier discussions on this project with Erkan Narmanli. M.N. was supported by
grants MTM2017-82166-P and PID2020-113082GB-I00, the Severo Ochoa and Mar´ıa de Maeztu Program
for Centers and Units of Excellence in R&D (CEX2020-001084-M). C.R. was supported by the grant Beatriu
de Pin´os BP2019, funded by the H2020 COFUND project No 801370 and AGAUR (the Catalan agency
for management of university and research grants), and the grant PID2020-113082GB-I00 of the Spanish
ministry of Science and Innovation.
dc.publisher
Elsevier B.V.
dc.relation.ispartof
Discrete Mathematics
dc.rights
L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: https://creativecommons.org/licenses/by/4.0/
dc.source
RECERCAT (Dipòsit de la Recerca de Catalunya)
dc.subject.other
Asymptotic enumeration, Chordal planar graphs, Subcritical graph class
dc.title
Enumeration of chordal planar graphs and maps
dc.type
info:eu-repo/semantics/article
dc.type
info:eu-repo/semantics/publishedVersion
dc.identifier.doi
10.1016/j.disc.2022.113163
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
