In graph-theoretic 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 (2008).
Read more about Distance-hereditary Graph: Definition and Characterization, Relation To Other Graph Families, Algorithms
Famous quotes containing the word graph:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)