Triangles in random cubic planar graphs. (English) Zbl 1346.05277
Nešetril, Jaroslav (ed.) et al., Extended abstracts of the eight European conference on combinatorics, graph theory and applications, EuroComb 2015, Bergen, Norway, August 31 – September 4, 2015. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 49, 383-391, electronic only (2015).
Summary: In this extended abstract we determine a normal limiting distribution for the number of triangles in a uniformly at random 3-connected cubic planar graph, as well as the precise expectation and variance values. Further comments towards the more complicated problem of studying both the limiting distribution of triangles in random cubic planar graphs, and the (asymptotic) number of triangle-free cubic planar graphs are discussed as well.
For the entire collection see [Zbl 1329.05004].
For the entire collection see [Zbl 1329.05004].
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
References:
| [1] | Banderier, C.; Flajolet, P.; Schaeffer, G.; Soria, M., Random maps, coalescing saddles, singularity analysis, and airy phenomena, Random Structures and Algorithms, 19, 194-246 (2001) · Zbl 1016.68179 |
| [2] | Bender, E. A.; Gao, Z.; Wormald, N. C., The number of 2-connected labelled planar graphs, Electron. J. Combin., 9, 194-246 (2002) |
| [3] | Bodirsky, M.; Giménez, O.; Kang, M.; Noy, M., Enumeration and limit laws for series-parallel graphs, European Journal of Combinatorics, 28, 8, 2091-2105 (2007) · Zbl 1127.05052 |
| [4] | Bodirsky, M.; Kang, M.; Löffler, M.; McDiarmid, C., Random cubic planar graphs, Random Structures and Algorithms, 30, 1-2, 78-94 (2007) · Zbl 1114.05094 |
| [5] | Bollobás, B., Random graphs, Cambridge Studies in Advanced Mathematics, vol. 73 (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0997.05049 |
| [6] | Chapuy, G.; Fusy, E.; Giménez, O.; Mohar, B.; Noy, M., Asymptotic enumeration and limit laws for graphs of fixed genus, Journal of Combinatorial Theory, Series A, 118, 3, 748-777 (2011) · Zbl 1231.05179 |
| [7] | Denise, A.; Vasconcellos, M.; Welsh, D., The random planar graph, Congr. Numer., 113, 61-79 (1996) · Zbl 0973.05066 |
| [8] | Drmota, M., Random trees: an interplay between combinatorics and probability (2009), Springer: Springer Wien-New York · Zbl 1170.05022 |
| [9] | Erdős, P.; Rényi, A., On the evolution of random graphs, (Publication of the Mathematical Institute of the Hungarian Academy of Sciences (1960)), 17-61 · Zbl 0103.16301 |
| [10] | Flajolet, P.; Sedgewick, R., Analytic combinatorics (2009), Cambridge University Press · Zbl 1165.05001 |
| [11] | Gao, Z.; Wormald, N. C., Enumeration of rooted cubic planar maps, Annals of Combinatorics, 6, 313-325 (2002) · Zbl 1017.05050 |
| [12] | Gao, Z.; Wormald, N. C., Asymptotic normality determined by high moments, and submap counts of random maps, Probab. Theory Related Fields, 130, 3, 368-376 (2004) · Zbl 1058.60015 |
| [13] | Gao, Z.; Wormald, N. C., Distribution of subgraphs of random regular graphs, Random Structures Algorithms, 32, 1, 38-48 (2008) · Zbl 1131.05084 |
| [14] | Giménez, O.; Noy, M., Asymptotic enumeration and limit laws of planar graphs, Journal of the American Mathematical Society, 22, 2, 309-329 (2009) · Zbl 1206.05019 |
| [15] | Giménez, O.; Noy, M.; Rué, J., Graph classes with given 3-connected components: asymptotic enumeration and random graphs, Random Structures Algorithms, 42, 4, 438-479 (2013) · Zbl 1269.05060 |
| [16] | Hwang, H.-K., On convergence rates in the central limit theorems for combinatorial structures, European Journal of Combinatorics, 19, 3, 329-343 (1998) · Zbl 0906.60024 |
| [17] | Janson, S.; Łuczak, T.; Rucinski, A., Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (2000), Wiley-Interscience: Wiley-Interscience New York · Zbl 0968.05003 |
| [18] | McDiarmid, C., Random graphs from a minor-closed class, Combin. Probab. Comput., 18, 4, 583-599 (2009) · Zbl 1215.05167 |
| [19] | McDiarmid, C.; Steger, A.; Welsh, D. J., Random planar graphs, Journal of Combinatorial Theory, Series B, 93, 187-205 (2005) · Zbl 1056.05128 |
| [20] | Tutte, W. T., A census of planar triangulations, Canadian Journal of Mathematics, 14, 21-38 (1962) · Zbl 0103.39603 |
| [21] | Tutte, W. T., A census of planar maps, Candian Journal of Mathematics, 15, 249-271 (1963) · Zbl 0115.17305 |
| [22] | Tutte, W. T., On the enumeration of planar maps, Bulletin of the American Mathematical Society, 74, 64-74 (1968) · Zbl 0157.31101 |
| [23] | Whitney, H., Congruent graphs and the connectivity of graphs, American Journal of Mathematics, 54, 150-168 (1932) · JFM 58.0609.01 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
