Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way - (Extended Abstract).
Serafino Cicerone · Theory and Applications of Models of Computation · 2011
In this paper we introduce a new graph class denoted as Gen(∗;P3,C3,C5). It contains all graphs that can be generated via split composition by using paths P3 and cycles C3 and C5 as components. This new graph class extends the well known class of distance-hereditary graphs, which corresponds to Gen(∗;P3,C3). For the new class we pro- vide efficient algorithms for several basic combinatorial problems: recog- nition, stretch number, stability number, clique number, domination number, chromatic number, graph isomorphism, and clique width.