Interval Graph - Definition

Definition

Let {I1, I2, ..., In} ⊂ P(R) be a set of intervals.

The corresponding interval graph is G = (V, E), where

  • V = {I1, I2, ..., In}, and
  • {Iα, Iβ} ∈ E if and only if IαIβ ≠ ∅.

From this construction one can verify a common property held by all interval graphs. That is, graph G is an interval graph if and only if the maximal cliques of G can be ordered M1, M2, ..., Mk such that for any vMiMk, where i < k, it is also the case that vMj for any Mj, ijk.

Read more about this topic:  Interval Graph

Famous quotes containing the word definition:

    It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.”
    Jane Adams (20th century)

    It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.
    François, Duc De La Rochefoucauld (1613–1680)

    The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.
    Jean Baudrillard (b. 1929)