Distance-hereditary digraphs

AbstractExtending notions from undirected graphs, we introduce directed graphs with the property that distances are preserved when taking induced subdigraphs. We characterize these distance-hereditary digraphs in terms of paths, their level structure and forbidden induced subdigraphs. Weaker requirements than the preservation of distances allow the distance to increase by a multiplicative or additive constant. For these (k,{+,∗})-distance-hereditary digraphs we give characterizations and provide computational complexity results for the corresponding recognition problems