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:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)