A complete grammar for decomposing a family of graphs into 3-connected components (Q1010886): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 22:14, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A complete grammar for decomposing a family of graphs into 3-connected components |
scientific article |
Statements
A complete grammar for decomposing a family of graphs into 3-connected components (English)
0 references
7 April 2009
0 references
Summary: \textit{W.T. Tutte} has described in the book ``Connectivity in graphs'' [Math. Expositions 15, Toronto: Univ. Toronto Press; London: Oxf. Univ. Press. IX, 145 p. (1966; Zbl 0146.45603)] a canonical decomposition of any graph into 3-connected components. In this article we translate (using the language of symbolic combinatorics) Tutte's decomposition into a general grammar expressing any family \({\mathcal G}\) of graphs (with some stability conditions) in terms of the subfamily \({\mathcal G}_3\) of graphs in \({\mathcal G}\) that are 3-connected (until now, such a general grammar was only known for the decomposition into 2-connected components). As a byproduct, our grammar yields an explicit system of equations to express the series counting a (labelled) family of graphs in terms of the series counting the subfamily of 3-connected graphs. A key ingredient we use is an extension of the so-called dissymmetry theorem, which yields negative signs in the grammar and associated equation system, but has the considerable advantage of avoiding the difficult integration steps that appear with other approaches, in particular in recent work by \textit{O. Giménez} and \textit{M. Noy}, ``Asymptotic enumeration and limit laws of planar graphs'', arXiv:math/0501269 (2005)] on counting planar graphs. As a main application we recover in a purely combinatorial way the analytic expression found by Giménez and Noy for the series counting labelled planar graphs (such an expression is crucial to do asymptotic enumeration and to obtain limit laws of various parameters on random planar graphs). Besides the grammar, an important ingredient of our method is a recent bijective construction of planar maps by Bouttier, Di Francesco and Guitter. Finally, our grammar applies also to the case of unlabelled structures, since the dissymetry theorem takes symmetries into account. Even if there are still difficulties in counting unlabelled 3-connected planar graphs, we think that our grammar is a promising tool toward the asymptotic enumeration of unlabelled planar graphs, since it circumvents some difficult integral calculations.
0 references
graph decomposition
0 references
3-connected components
0 references
symbolic combinatorics
0 references
grammar
0 references
family of graphs
0 references
subfamily of graphs
0 references
dissymmetry theorem
0 references
series counting labellled planar graphs
0 references
asymptotic enumeration
0 references
unlabelled planar graphs
0 references
bijective construction of planar graphs
0 references