Almost distance-hereditary graphs (Q5957743)

Distance-hereditary graphs (graphs in which the distances are preserved by induced subgraphs) have been introduced and characterized by \textit{E. Howorka} [Q. J. Math., Oxf. II. Ser. 28, 417-420 (1977; Zbl 0376.05040)]. Several characterizations involving metric properties have been obtained by \textit{H.-J. Bandelt} and \textit{H. M. Mulder} [J. Comb. Theory, Ser. B 41, 182-208 (1986; Zbl 0605.05024)]. In this paper the notion of distance-hereditary graphs is extended by introducing the class of almost distance-hereditary graphs (a very weak increase of the distance is allowed by induced subgraphs, i.e., for all connected induced subgraphs \(H=(Y,F)\) of \(G\), one has \(d_{H}(u,v)\leq d_{G}(u,v)+1\) for every \(u,v\in Y\)). A characterization of these graphs in terms of forbidden-induced subgraphs is obtained and other both combinatorial and metric properties are derived in the paper.