Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514562 | Electronic Notes in Discrete Mathematics | 2005 | 7 Pages |
Abstract
Given a simple and finite connected graph G, the distance dG(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 and H.M. Mulder, Distance Hereditary Graphs, J. Combin, Series B 41 (1986) 182-208] have characterized the class of distance hereditary graphs where the distance is preserved in each connected subgraph. In this paper, we are interested with 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â1) unities. We provide a characterization of k-distance hereditary graphs in terms of forbidden configurations for each kâNâ.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kahina Meslem, Méziane Aïder,