Name
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^{lceil 3.59nrceil}}$. In this paper, using classical tools of enumerative combinatorics, we improve on this result by providing an exact enumeration of distance-hereditary graphs, which allows to show that the number of distance-hereditary graphs on $n$ vertices is tightly bounded by ${(7.24975ldots)^n}$---opening the perspective such graphs could be encoded on $3n$ bits. We also provide the exact enumeration and asymptotics 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/1.9781611974775.3 | analytic algorithmics and combinatorics |
DocType | Volume | Citations |
Conference | abs/1608.01464 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| cedric chauve | 1 | 429 | 41.81 |
| Éric Fusy | 2 | 198 | 21.95 |
| Jérémie Lumbroso | 3 | 12 | 3.92 |