Split-decomposition trees with prime nodes: Enumeration and random generation of cactus graphs

Maryam Bahrani, Jérémie Lumbroso

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 languageEnglish (US)
Title of host publication2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018
EditorsMarkus Nebel, Stephan Wagner
PublisherSociety for Industrial and Applied Mathematics Publications
Pages143-157
Number of pages15
ISBN (Electronic)9781611975062
DOIs
StatePublished - 2018
Event15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018 - New Orleans, United States
Duration: Jan 8 2018Jan 9 2018

Publication series

Name2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018
Volume2018-January

Conference

Conference15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018
CountryUnited States
CityNew Orleans
Period1/8/181/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

    Bahrani, M., & Lumbroso, J. (2018). Split-decomposition trees with prime nodes: Enumeration and random generation of cactus graphs. In M. Nebel, & S. Wagner (Eds.), 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