Distance-hereditary Graph - Relation To Other Graph Families

Relation To Other Graph Families

Every distance-hereditary graph is a perfect graph and more specifically a perfectly orderable graph. Every distance-hereditary graph is also a parity graph, a graph in which every two induced paths between the same pair of vertices both have odd length or both have even length. Every even power of a distance-hereditary graph G (that is, the graph G2i formed by connecting pairs of vertices at distance at most 2i in G) is a chordal graph.

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; they include as a special case the block 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.