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

MaRDI QIDQ1010886zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/0808.1138, https://eudml.org/doc/117283, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r148.html

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

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)

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.

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

Cited in

(18)

• Asymptotic enumeration and limit laws for graphs of fixed genus
• 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
• Characterisation of symmetries of unlabelled triangulations
• Limit laws of planar maps with prescribed vertex degrees
• 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

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)