A complete grammar for decomposing a family of graphs into 3-connected components

zbMATH Open1178.05054arXiv0808.1138MaRDI QIDQ1010886FDOQ1010886

Authors: Guillaume Chapuy, Éric Fusy, Mihyun Kang, Bilyana Shoilekova 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Tutte has described in the book "Connectivity in graphs" 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 of graphs (with some stability conditions) in terms of the 3-connected subfamily. A key ingredient we use is an extension of the so-called dissymmetry theorem, which yields negative signs in the grammar. As a main application we recover in a purely combinatorial way the analytic expression found by Gim'enez 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.

Full work available at URL: https://arxiv.org/abs/0808.1138

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Structure and enumeration of two-connected graphs with prescribed three-connected components
• scientific article; zbMATH DE number 1735656
• Enumeration of chordal planar graphs and maps
• Enumerative applications of a decomposition for graphs and digraphs
• Counting planar graphs and related families of graphs

zbMATH Keywords

grammargraph decompositionasymptotic enumeration3-connected componentsbijective construction of planar graphsdissymmetry theoremfamily of graphsseries counting labellled planar graphssubfamily of graphssymbolic combinatoricsunlabelled planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Connectivity (05C40)

Cited In (18)

• Spanning trees in random series-parallel graphs
• Random graphs from a weighted minor-closed class
• Structure and enumeration of two-connected graphs with prescribed three-connected components
• Exact-Size Sampling of Enriched Trees in Linear Time
• Generating functions of bipartite maps on orientable surfaces
• Enumeration of chordal planar graphs and maps
• Limit laws of planar maps with prescribed vertex degrees
• Characterisation of symmetries of unlabelled triangulations
• Random cubic planar graphs revisited
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Local convergence of random planar graphs
• The maximum degree of random planar graphs
• Chordal graphs with bounded tree-width
• Symmetries of unlabelled planar triangulations
• Local convergence of random planar graphs
• Enumerations, forbidden subgraph characterizations, and the split-decomposition
• Asymptotic enumeration and limit laws for graphs of fixed genus

This page was built for publication: A complete grammar for decomposing a family of graphs into 3-connected components

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010886)