Maximal connected cographs in distance-hereditary graphs

Abstract

A graph is distance-hereditary if the distance between two vertices in every connected induced subgraph always equals their distance in the full graph. Recent work by F. Nicolai implies that being distance-hereditary is equivalent to having a certain tree structure defined in terms of the maximal complement-reducible (cograph) subgraphs, paralleling the characterization of chordal graphs by clique trees. Several characterizations are given for a sense of 'strongly distance-hereditary graphs' that parallels strongly chordal graphs.