Exponential bounds on graph enumerations from vertex incremental characterizations

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ⁿ, to be compared with the precise exponential growth, ∼ 6.159ⁿ, 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.