An extension of distance hereditary graphs

A distance hereditary graph is a graph in which the distance is preserved by any connected induced subgraph. This notion has been adapted to the bipartite graphs to define the class of k- bipartite distance hereditary graphs, noted k-BDHG, where the length of the shortest {u, v}-path is at most d(u, v) + 2k. When k = 1, a characterization has been obtained in terms of forbidden induced subgraphs. We use this characterization to give two polynomial time algorithms to recognize this class of graphs. We give also a characterization of k- BDHG in terms of forbidden configurations and we conclude with some open problems.

Page du séminaire compréhensible : http://www-fourier.ujf-grenoble.fr/~magotjm/seminaire_comprehensible/ind...