On an extension of distance hereditary graphs

Given a simple and finite connected graph G , the distance d G ( u , v ) is the length of the shortest induced { u , v } -path linking the vertices u and v in G . Bandelt and Mulder [H.J. Bandelt, H.M. Mulder, Distance hereditary graphs, J. Combin. Theory Ser. B 41 (1986) 182–208] have characterized the class of distance hereditary graphs where the distance is preserved in each connected induced subgraph. In this paper, we are interested in the class of k -distance hereditary graphs ( k ∈ N ) which consists in a parametric extension of the distance heredity notion. We allow the distance in each connected induced subgraph to increase by at most k . We provide a characterization of k -distance hereditary graphs in terms of forbidden configurations for each k ≥ 2 .