2017/11/28 by Maryam Bahrani, Jérémie Lumbroso, Bahrani, Maryam +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1711.10647
15 pages, 8 figures, Maple code; published at ANALCO 2018
openalex publication_date 2017/11/28 · arxiv created 2017/11/29 · arxiv updated 2017/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we build on recent results by Chauve et al. (2014) and Bahrani and Lumbroso (2017), which combined the split-decomposition, 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 (2015).