In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph)[1] 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.[2]
It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs,[3] but no intersection model was known until one was given by Gioan & Paul (2012).
- ^ Hammer & Maffray (1990).
- ^ Olaru and Sachs showed the α-perfection of the graphs in which every cycle of length five or more has a pair of crossing diagonals (Sachs 1970, Theorem 5). By Lovász (1972), α-perfection is an equivalent form of definition of perfect graphs.
- ^ McKee & McMorris (1999)