Distance-hereditary graphs were named and first studied by , although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs.
Distance-hereditary graphs may also be characterized in several other equivalent ways:
Every distance-hereditary graph may be represented as the intersection graph of chords on a circle, forming a circle graph. This may be seen by building up the graph by adding pendant vertices, false twins, and true twins, at each step building up a corresponding set of chords representing the graph. Adding a pendant vertex corresponds to adding a chord near the endpoints of an existing chord so that it crosses only that chord; adding false twins corresponds to replacing a chord by two parallel chords crossing the same set of other chords; and adding true twins corresponds to replacing a chord by two chords that cross each other but are nearly parallel and cross the same set of other chords.
A distance-hereditary graph is bipartite if and only if it is triangle-free. Bipartite distance-hereditary graphs may be built up from a single vertex by adding only pendant vertices and false twins, since any true twin would form a triangle, but the pendant vertex and false twin operations preserve bipartiteness.
The graphs that may be built from a single vertex by pendant vertices and true twins, without any false twin operations, are the chordal distance-hereditary graphs, also called ptolemaic graphs. The graphs that may be built from a single vertex by false twin and true twin operations, without any pendant vertices, are the cographs, which are therefore distance-hereditary; the cographs are exactly the disjoint unions of diameter-2 distance-hereditary graphs. The neighborhood of any vertex in a distance-hereditary graph is a cograph. The transitive closure of the directed graph formed by choosing any set of orientations for the edges of any tree is distance-hereditary; the special case in which the tree is oriented consistently away from some vertex forms a subclass of distance-hereditary graphs known as the trivially perfect graphs, which may equivalently be described as chordal cographs.
Because distance-hereditary graphs are perfect, some optimization problems may be solved in polynomial time for them despite being NP-hard for more general classes of graphs. Thus, it is possible in polynomial time to find the maximum clique or maximum independent set in a distance-hereditary graph, or to find an optimal graph coloring of any distance-hereditary graph. Because distance-hereditary graphs are circle graphs, they inherit polynomial time algorithms for circle graphs; for instance, it is possible determine in polynomial time the treewidth of any circle graph and therefore of any distance-hereditary graph. Additionally, the clique-width of any distance-hereditary graph is at most three. As a consequence, efficient dynamic programming algorithms exist for many problems on these graphs.
Several other optimization problems may also be solved more efficiently using algorithms specifically designed for distance-hereditary graphs. As show, a minimum connected dominating set (or equivalently a spanning tree with the maximum possible number of leaves) may be found in polynomial time on a distance-hereditary graph. A Hamiltonian cycle or Hamiltonian path of any distance-hereditary graph may also be found in polynomial time.
| doi = 10.1016/j.disopt.2005.03.004}}.
| doi = 10.1016/S0304-3975(00)00234-6}}.
| doi = 10.1142/S0129054100000260}}.
| doi = 10.1016/0166-218X(90)90131-U}}.
| url = http://qjmath.oxfordjournals.org/cgi/reprint/28/4/417 | doi = 10.1093/qmath/28.4.417}}.
| doi = 10.1016/0020-0190(93)90100-N}}.
| doi = 10.1016/j.jctb.2005.03.003}}.