@inproceedings{5acb3742362e447c865eb842945d3976,

title = "An exact enumeration of distance-hereditary graphs",

abstract = "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.",

author = "C{\'e}dric Chauve and {\'E}ric Fusy and J{\'e}r{\'e}mie Lumbroso",

year = "2017",

month = jan,

day = "1",

language = "English (US)",

series = "14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "31--45",

editor = "Conrado Martinez and Ward, {Mark Daniel}",

booktitle = "14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017",

address = "United States",

note = "14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017 ; Conference date: 16-01-2017 Through 17-01-2017",

}