Recognition of probe distance-hereditary graphs

Let GG denote a graph class. An undirected graph GG is called a probe GG graph if one can make GG a graph in GG by adding edges between vertices in some independent set of GG. By definition graph class GG is a subclass of probe GG 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)O(nm)-time algorithms to recognize probe distance-hereditary graphs and probe bipartite distance-hereditary graphs where nn and mm are the numbers of vertices and edges of the input graph respectively.