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

Original language | English (US) |
---|---|

Title of host publication | 14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017 |

Editors | Conrado Martinez, Mark Daniel Ward |

Publisher | Society for Industrial and Applied Mathematics Publications |

Pages | 31-45 |

Number of pages | 15 |

ISBN (Electronic) | 9781611974775 |

State | Published - Jan 1 2017 |

Event | 14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017 - Barcelona, Spain Duration: Jan 16 2017 → Jan 17 2017 |

### Publication series

Name | 14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017 |
---|

### Conference

Conference | 14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017 |
---|---|

Country | Spain |

City | Barcelona |

Period | 1/16/17 → 1/17/17 |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Materials Chemistry
- Applied Mathematics

## Fingerprint Dive into the research topics of 'An exact enumeration of distance-hereditary graphs'. Together they form a unique fingerprint.

## Cite this

*14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017*(pp. 31-45). (14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017). Society for Industrial and Applied Mathematics Publications.