Recognition of probe distance-hereditary graphs

Let g, denote a graph class. An undirected graph G is called a probe g, graph if one can make G a graph in g, by adding edges between vertices in some independent set of G. By definition graph class g, is a subclass of probe g graphs. A graph is distance hereditary if the distance between any two vertices remains the same in every connected induced subgraph. Bipartite distance-hereditary graphs are both bipartite and distance hereditary. In this paper we propose O(nm)-time algorithms to recognize probe distance-hereditary graphs and probe bipartite distance-hereditary graphs where n and m are the numbers of vertices and edges of the input graph respectively. (C) 2012 Elsevier B.V. All rights reserved.