### Abstract

In this paper, we build on recent results by Chauve et al. and Bahrani and Lumbroso, which combined the splitdecomposition, as exposed by Gioan and Paul, with analytic combinatorics, to produce new enumerative results on graphs-in particular the enumeration of several subclasses of perfect graphs (distance-hereditary, 3-leaf power, ptolemaic). Our goal was to study a simple family of graphs, of which the split-decomposition trees have prime nodes drawn from an enumerable (and manageable!) set of graphs. Cactus graphs, which we describe in more detail further down in this paper, can be thought of as trees with their edges replaced by cycles (of arbitrary lengths). Their split-decomposition trees contain prime nodes that are cycles, making them ideal to study. We derive a characterization for the split-decomposition trees of cactus graphs, produce a general template of symbolic grammars for cactus graphs, and implement random generation for these graphs, building on work by Iriza.

Original language | English (US) |
---|---|

Title of host publication | 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018 |

Editors | Markus Nebel, Stephan Wagner |

Publisher | Society for Industrial and Applied Mathematics Publications |

Pages | 143-157 |

Number of pages | 15 |

ISBN (Electronic) | 9781611975062 |

DOIs | |

State | Published - 2018 |

Event | 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018 - New Orleans, United States Duration: Jan 8 2018 → Jan 9 2018 |

### Publication series

Name | 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018 |
---|---|

Volume | 2018-January |

### Conference

Conference | 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018 |
---|---|

Country | United States |

City | New Orleans |

Period | 1/8/18 → 1/9/18 |

### All Science Journal Classification (ASJC) codes

- Materials Chemistry
- Applied Mathematics
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Split-decomposition trees with prime nodes: Enumeration and random generation of cactus graphs'. Together they form a unique fingerprint.

## Cite this

*2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018*(pp. 143-157). (2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018; Vol. 2018-January). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611975062.13