๐ฎ
๐ฎ
The Ethereal
Enumeration of chordal planar graphs and maps
February 27, 2022 ยท The Ethereal ยท ๐ Discrete Mathematics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Jordi Castellvรญ, Marc Noy, Clรฉment Requilรฉ
arXiv ID
2202.13340
Category
math.CO: Combinatorics
Cross-listed
cs.DS
Citations
1
Venue
Discrete Mathematics
Last Checked
3 months ago
Abstract
We determine the number of labelled chordal planar graphs with $n$ vertices, which is asymptotically $c_1\cdot n^{-5/2} ฮณ^n n!$ for a constant $c_1>0$ and $ฮณ\approx 11.89235$. We also determine the number of rooted simple chordal planar maps with $n$ edges, which is asymptotically $c_2 n^{-3/2} ฮด^n$, where $ฮด= 1/ฯ\approx 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 $K_4$ by repeatedly adding vertices adjacent to an existing triangular face.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal