Distance-hereditary graph

The graphs that can be built from a single vertex by false twin and true twin operations, without any pendant vertices, are the cographs, which are therefore distance-hereditary; the cographs are exactly the disjoint unions of diameter-2 distance-hereditary graphs.

[12] Distance-hereditary graphs can be recognized, and parsed into a sequence of pendant vertex and twin operations, in linear time.

[16] As a consequence, by Courcelle's theorem, efficient dynamic programming algorithms exist for many problems on these graphs.

[17] Several other optimization problems can also be solved more efficiently using algorithms specifically designed for distance-hereditary graphs.

As D'Atri & Moscarini (1988) show, a minimum connected dominating set (or equivalently a spanning tree with the maximum possible number of leaves) can be found in polynomial time on a distance-hereditary graph.