Exponential bounds on graph enumerations from vertex incremental characterizations

Jérémie Lumbroso, Jessica Shi

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

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.301n, to be compared with the precise exponential growth, ∼ 6.159n, 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 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
Pages118-132
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
  • 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

    Lumbroso, J., & Shi, J. (2018). Exponential bounds on graph enumerations from vertex incremental characterizations. In M. Nebel, & S. Wagner (Eds.), 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