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.
@article{10_37236_6431,
author = {Maryam Bahrani and J\'er\'emie Lumbroso},
title = {Enumerations, forbidden subgraph characterizations, and the split-decomposition},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {4},
doi = {10.37236/6431},
zbl = {1409.05106},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6431/}
}
TY - JOUR
AU - Maryam Bahrani
AU - Jérémie Lumbroso
TI - Enumerations, forbidden subgraph characterizations, and the split-decomposition
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/6431/
DO - 10.37236/6431
ID - 10_37236_6431
ER -
%0 Journal Article
%A Maryam Bahrani
%A Jérémie Lumbroso
%T Enumerations, forbidden subgraph characterizations, and the split-decomposition
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6431/
%R 10.37236/6431
%F 10_37236_6431
Maryam Bahrani; Jérémie Lumbroso. Enumerations, forbidden subgraph characterizations, and the split-decomposition. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/6431
