Distance-hereditary graph

In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. Distance-hereditary graphs were named and first studied by Howorka (1977), although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs. It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs, but no intersection model was known until one was given by Gioan & Paul (2012). The original definition of a distance-hereditary graph is a graph G such that, if any two vertices u and v belong to a connected induced subgraph H of G, then some shortest path connecting u and v in G must be a subgraph of H, so that the distance between u and v in H is the same as the distance in G. Distance-hereditary graphs can also be characterized in several other equivalent ways: Every distance-hereditary graph is a perfect graph, more specifically a perfectly orderable graph and a Meyniel 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 can be represented as the intersection graph of chords on a circle, forming a circle graph. This can 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 can 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. Every bipartite distance-hereditary graph is chordal bipartite and modular. The graphs that can be built from a single vertex by pendant vertices and true twins, without any false twin operations, are special cases of the Ptolemaic graphs and include the block graphs. The graphs that can 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 are also called chordal cographs.