کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648589 | 1342418 | 2009 | 9 صفحه PDF | دانلود رایگان |
Given a simple and finite connected graph GG, the distance dG(u,v)dG(u,v) is the length of the shortest induced {u,v}{u,v}-path linking the vertices uu and vv in GG. 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 kk-distance hereditary graphs (k∈N)(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 kk. We provide a characterization of kk-distance hereditary graphs in terms of forbidden configurations for each k≥2k≥2.
Journal: Discrete Mathematics - Volume 309, Issue 11, 6 June 2009, Pages 3644–3652