Chordal graphs with bounded tree-width

EUROCOMB’23

Jordi Castellví Michael Drmota Marc Noy Clément Requilé

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-037

PDF
Abstract
Given $t\ge 2$ and $0\le k\le t$, we prove that the number of labelled $k$-connected chordal graphs with $n$ vertices and tree-width at most $t$ is asymptotically $c n^{-5/2} \gamma^n n!$, as $n\to\infty$, for some constants $c,\gamma >0$ depending on $t$ and $k$. Additionally, we show that the number of $i$-cliques ($2\le i\le t$) in a uniform random $k$-connected chordal graph with tree-width at most $t$ is normally distributed as $n\to\infty$. The asymptotic enumeration of graphs of tree-width at most $t$ is wide open for $t\ge 3$. To the best of our knowledge, this is the first non-trivial class of graphs with bounded tree-width where the asymptotic counting problem is solved. Our starting point is the work of Wormald [Counting Labelled Chordal Graphs, Graphs and Combinatorics (1985)], were an algorithm is developed to obtain the exact number of labelled chordal graphs on $n$ vertices..

Pages:
270–276
References

D. Aldous. The Continuum Random Tree. I. The Annals of Probability, 19(1):1 - 28, 1991.
https://doi.org/10.1214/aop/1176990534

J. Baste, M. Noy, and I. Sau. On the number of labeled graphs of bounded treewidth. European Journal of Combinatorics, 71:12-21, 2018.
https://doi.org/10.1016/j.ejc.2018.02.030

L. W. Beineke and R. E. Pippert. The number of labeled k-dimensional trees. Journal of Combinatorial Theory, 6(2):200-205, 1969.
https://doi.org/10.1016/S0021-9800(69)80120-1

E. A. Bender, L. B. Richmond, and N. C. Wormald. Almost all chordal graphs split. Australian Mathematical Society. Journal. Series A. Pure Mathematics and Statistics, 38(2):214-221, 1985.
https://doi.org/10.1017/S1446788700023077

M. Bodirsky, O. Giménez, M. Kang, and M. Noy. Enumeration and limit laws for series-parallel graphs. European Journal of Combinatorics, 28(8):2091-2105, 2007.
https://doi.org/10.1016/j.ejc.2007.04.011

J. Castellví, M. Drmota, M. Noy, and C. Requilé. Chordal graphs with bounded tree-width. 2023. arXiv:2301.00194.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-037

J. Castellví, M. Noy, and C. Requilé. Enumeration of chordal planar graphs and maps. Discrete Mathematics, 346(1):113163, 2023.
https://doi.org/10.1016/j.disc.2022.113163

M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015.
https://doi.org/10.1007/978-3-319-21275-3

R. Diestel. Graph Theory. Springer Berlin, Heidelberg, Fifth edition, 2016.

G. A. Dirac. On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25:71-76, 1961.
https://doi.org/10.1007/BF02992776

M. Drmota. Random Trees. Springer-Verlag Wien, 2009.
https://doi.org/10.1007/978-3-211-75357-6

M. Drmota, E. Fusy, M. Kang, V. Kraus, and J. Rué. Asymptotic study of subcritical graph classes. SIAM Journal on Discrete Mathematics, 25(4):1615-1651, 2011.
https://doi.org/10.1137/100790161

Z. Dvořák and S. Norine. Small graph classes and bounded expansion. Journal of Combinatorial Theory. Series B, 100(2):171-175, 2010.
https://doi.org/10.1016/j.jctb.2009.06.001

P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2009.
https://doi.org/10.1017/CBO9780511801655

D. Foata. Enumerating k-trees. Discrete Mathematics, 1(2):181-186, 1971.
https://doi.org/10.1016/0012-365X(71)90023-9

M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, volume 57 of Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, second edition, 2004. With a foreword by Claude Berge.
https://doi.org/10.1016/S0167-5060(04)80051-7

J. W. Moon. The number of labeled k-trees. Journal of Combinatorial Theory, 6(2):196-199, 1969.
https://doi.org/10.1016/S0021-9800(69)80119-5

S. Norine, P. Seymour, R. Thomas, and P. Wollan. Proper minor-closed families are small. Journal of Combinatorial Theory. Series B, 96(5):754-757, 2006.
https://doi.org/10.1016/j.jctb.2006.01.006

K. Panagiotou, B. Stufler, and K. Weller. Scaling limits of random graphs from sub-critical classes. The Annals of Probability, 44(5):3291-3334, 2016.
https://doi.org/10.1214/15-AOP1048

N. C. Wormald. Counting labelled chordal graphs. Graphs and Combinatorics, 1(2):193-200, 1985.
https://doi.org/10.1007/BF02582944

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Jordi Castellví, Michael Drmota, Marc Noy, Clément Requilé

PDF