TY - GEN
T1 - An exact enumeration of distance-hereditary graphs
AU - Chauve, Cédric
AU - Fusy, Éric
AU - Lumbroso, Jérémie
N1 - Publisher Copyright:
© Copyright by SIAM.
PY - 2017
Y1 - 2017
N2 - Distance-hereditary graphs form an important class of graphs, from the theoretical point of view, due to the fact that they are the totally decomposable graphs for the split-decomposition. The previous best enumerative result for these graphs is from Nakano et al. (J. Comp. Sci. Tech., 2007), who have proven that the number of distance-hereditary graphs on n vertices is bounded by 2[3.59n]. In this paper, using classical tools of enumerative combinatorics, we improve on this result by providing an exact enumeration and full asymptotic of distance-hereditary graphs, which allows to show that the number of distance-hereditary graphs on n vertices is tightly bounded by (7.24975⋯)n - opening the perspective such graphs could be encoded on 3n bits. We also provide the exact enumeration and full asymptoticss of an important subclass, the 3-leaf power graphs. Our work illustrates the power of revisiting graph decomposition results through the framework of analytic combinatorics.
AB - Distance-hereditary graphs form an important class of graphs, from the theoretical point of view, due to the fact that they are the totally decomposable graphs for the split-decomposition. The previous best enumerative result for these graphs is from Nakano et al. (J. Comp. Sci. Tech., 2007), who have proven that the number of distance-hereditary graphs on n vertices is bounded by 2[3.59n]. In this paper, using classical tools of enumerative combinatorics, we improve on this result by providing an exact enumeration and full asymptotic of distance-hereditary graphs, which allows to show that the number of distance-hereditary graphs on n vertices is tightly bounded by (7.24975⋯)n - opening the perspective such graphs could be encoded on 3n bits. We also provide the exact enumeration and full asymptoticss of an important subclass, the 3-leaf power graphs. Our work illustrates the power of revisiting graph decomposition results through the framework of analytic combinatorics.
UR - http://www.scopus.com/inward/record.url?scp=85016567366&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85016567366&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974775.3
DO - 10.1137/1.9781611974775.3
M3 - Conference contribution
AN - SCOPUS:85016567366
T3 - 14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017
SP - 31
EP - 45
BT - 14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017
A2 - Martinez, Conrado
A2 - Ward, Mark Daniel
PB - Society for Industrial and Applied Mathematics Publications
T2 - 14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017
Y2 - 16 January 2017 through 17 January 2017
ER -