An exact enumeration of distance-hereditary graphs

Cédric Chauve, Éric Fusy, Jérémie Lumbroso

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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 languageEnglish (US)
Title of host publication14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017
EditorsConrado Martinez, Mark Daniel Ward
PublisherSociety for Industrial and Applied Mathematics Publications
Pages31-45
Number of pages15
ISBN (Electronic)9781611974775
StatePublished - Jan 1 2017
Event14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 17 2017

Publication series

Name14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017

Conference

Conference14th Workshop on Analytic Algorithmics and Combinatorics 2017, ANALCO 2017
CountrySpain
CityBarcelona
Period1/16/171/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