### Abstract

In this paper, building on previous work by Nakano et al. [23], we develop an alternate technique which almost automatically translates (existing) vertex incremental characterizations of graph classes into asymptotics of that class. Specifically, we construct trees corresponding to the sequences of vertex incremental operations which characterize a graph class, and then use analytic combinatorics to enumerate the trees, giving an upper bound on the graph class. This technique is applicable to a wider set of graph classes compared to the tree decompositions, and we show that this technique produces accurate upper bounds. We first validate our method by applying it to the case of distance-hereditary graphs, and comparing the bound obtained by our method with that obtained by Nakano et al. [23], and the exact enumeration obtained by Chauve et al. [7, 8]. We then illustrate its use by applying it to switch cographs, for which there are few known results: our method provide a bound of ∼6.301^{n}, to be compared with the precise exponential growth, ∼ 6.159^{n}, which we obtained independently through the relationship between switch cographs and bicolored cographs, first introduced by Hertz [19]. We believe the popularity of vertex incremental characterizations might mean this may prove a fairly convenient to tool for future exploration of graph classes.

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 | 118-132 |

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
- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Exponential bounds on graph enumerations from vertex incremental characterizations'. Together they form a unique fingerprint.

## Cite this

*2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018*(pp. 118-132). (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.11