Almost distance-hereditary graphs Original Research Article

Distance-hereditary graphs (graphs in which the distances are preserved by induced subgraphs) have been introduced and characterized by Howorka. Several characterizations involving metric properties have been obtained by Bandelt and Mulder. In this paper, we extend the notion of distance-hereditary graphs by introducing the class of almost distance-hereditary graphs (a very weak increase of the distance is allowed by induced subgraphs). We obtain a characterization of these graphs in terms of forbidden-induced subgraphs and derive other both combinatorial and metric properties.