TY - GEN

T1 - Exponential bounds on graph enumerations from vertex incremental characterizations

AU - Lumbroso, Jérémie

AU - Shi, Jessica

N1 - Publisher Copyright:
© 2018 by SIAM.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85043483718&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85043483718&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975062.11

DO - 10.1137/1.9781611975062.11

M3 - Conference contribution

AN - SCOPUS:85043483718

T3 - 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

SP - 118

EP - 132

BT - 2018 Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

A2 - Nebel, Markus

A2 - Wagner, Stephan

PB - Society for Industrial and Applied Mathematics Publications

T2 - 15th Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018

Y2 - 8 January 2018 through 9 January 2018

ER -