Enumerations, forbidden subgraph characterizations, and the split-decomposition

zbMATH Open1409.05106arXiv1608.01465MaRDI QIDQ668013

Maryam Bahrani, Jérémie Lumbroso

Publication date: 5 March 2019

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

Abstract: Forbidden characterizations may sometimes be the most natural way to describe families of graphs, and yet these characterizations are usually very hard to exploit for enumerative purposes. By building on the work of Gioan and Paul (2012) and Chauve et al. (2014), we show a methodology by which we constrain a split-decomposition tree to avoid certain patterns, thereby avoiding the corresponding induced subgraphs in the original graph. We thus provide the grammars and full enumeration for a wide set of graph classes: ptolemaic, block, and variants of cactus graphs (2,3-cacti, 3-cacti and 4-cacti). In certain cases, no enumeration was known (ptolemaic, 4-cacti); in other cases, although the enumerations were known, an abundant potential is unlocked by the grammars we provide (in terms of asymptotic analysis, random generation, and parameter analyses, etc.). We believe this methodology here shows its potential; the natural next step to develop its reach would be to study split-decomposition trees which contain certain prime nodes. This will be the object of future work.

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

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

zbMATH Keywords

graph decompositionanalytic combinatoricsgraph enumerationsymbolic specification

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The on-line encyclopedia of integer sequences
• A complete grammar for decomposing a family of graphs into 3-connected components
• The number of trees
• A Characterization of Block-Graphs
• Finding kth paths and p-centers by generating and searching good data structures
• A characterization of ptolemaic graphs
• Decomposition of Directed Graphs
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• A calculus for the random generation of labelled combinatorial structures
• Boltzmann Samplers, Pólya Theory, and Cycle Pointing
• Boltzmann Sampling of Unlabelled Structures
• Forbidden subgraphs in connected graphs
• Enumeration of bipartite graphs and bipartite blocks
• On graphs without a \(C_{4}\) or a diamond
• The enumeration of bipartite graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• On the Number of Husimi Trees
• Asymptotic enumeration of cographs
• Laminar structure of ptolemaic graphs with applications
• A Characterization of Certain Ptolemaic Graphs
• Enumeration of \(m\)-ary cacti
• Asymptotic Properties of Some Minor-Closed Classes of Graphs
• Enumeration of \(P_4\)-free chordal graphs
• The domatic number of block-cactus graphs
• An Exact Enumeration of Distance-Hereditary Graphs
• Split-Decomposition Trees with Prime Nodes: Enumeration and Random Generation of Cactus Graphs

Cited In (2)

• Word-representability of graphs with respect to split recomposition
• Kazhdan-Lusztig polynomials of braid matroids

Uses Software

• OEIS

Recommendations

• Enumerative applications of a decomposition for graphs and digraphs 👍 👎
• On forbidden subdivision characterizations of graph classes 👍 👎
• Forbidden subgraphs and forbidden substructures 👍 👎
• Forbidden subgraphs and graph decomposition 👍 👎
• Splits with forbidden subgraphs 👍 👎
• A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs 👍 👎
• Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Enumerations, forbidden subgraph characterizations, and the split-decomposition

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