Enumerations, forbidden subgraph characterizations, and the split-decomposition
From MaRDI portal
(Redirected from Publication:668013)
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.
Recommendations
- On forbidden subdivision characterizations of graph classes
- scientific article; zbMATH DE number 4144022
- Forbidden subgraphs and graph decomposition
- Combinatorial enumeration of subdivisible graphs
- Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs
- Forbidden subgraphs and forbidden substructures
- A forbidden subgraphs characterization and a polynomial algorithm for randomly decomposable graphs
- Enumerative applications of a decomposition for graphs and digraphs
- Splits with forbidden subgraphs
- scientific article; zbMATH DE number 734480
Cites work
- scientific article; zbMATH DE number 1111371 (Why is no real title available?)
- scientific article; zbMATH DE number 3419161 (Why is no real title available?)
- A Characterization of Block-Graphs
- A Characterization of Certain Ptolemaic Graphs
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- A calculus for the random generation of labelled combinatorial structures
- A characterization of ptolemaic graphs
- A complete grammar for decomposing a family of graphs into 3-connected components
- An exact enumeration of distance-hereditary graphs
- Analytic combinatorics
- Asymptotic Properties of Some Minor-Closed Classes of Graphs
- Asymptotic enumeration of cographs
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Boltzmann Samplers, Pólya Theory, and Cycle Pointing
- Boltzmann sampling of unlabelled structures
- Decomposition of Directed Graphs
- Enumeration of \(P_4\)-free chordal graphs
- Enumeration of \(m\)-ary cacti
- Enumeration of bipartite graphs and bipartite blocks
- Finding kth paths and p-centers by generating and searching good data structures
- Forbidden subgraphs in connected graphs
- Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
- Laminar structure of ptolemaic graphs with applications
- On graphs without a \(C_{4}\) or a diamond
- On the Number of Husimi Trees
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Split-decomposition trees with prime nodes: enumeration and random generation of cactus graphs
- The domatic number of block-cactus graphs
- The enumeration of bipartite graphs
- The number of trees
- The on-line encyclopedia of integer sequences
- Trees
Cited in
(3)
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)
