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.

Read more about this topic:  Distance-hereditary Graph

Famous quotes containing the words relation to, relation, graph and/or families:

    Science is the language of the temporal world; love is that of the spiritual world. Man, indeed, describes more than he explains; while the angelic spirit sees and understands. Science saddens man; love enraptures the angel; science is still seeking, love has found. Man judges of nature in relation to itself; the angelic spirit judges of it in relation to heaven. In short to the spirits everything speaks.
    HonorĂ© De Balzac (1799–1850)

    When needs and means become abstract in quality, abstraction is also a character of the reciprocal relation of individuals to one another. This abstract character, universality, is the character of being recognized and is the moment which makes concrete, i.e. social, the isolated and abstract needs and their ways and means of satisfaction.
    Georg Wilhelm Friedrich Hegel (1770–1831)

    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)

    The man who promised to reinforce American families is now eager to pull the plug on Big Bird and Barney.
    Leslie Harris, U.S. political activist. As quoted in Newsweek magazine, p. 23 (December 19, 1994)