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:

    Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.
    Willard Van Orman Quine (b. 1908)

    The definition of good prose is proper words in their proper places; of good verse, the most proper words in their proper places. The propriety is in either case relative. The words in prose ought to express the intended meaning, and no more; if they attract attention to themselves, it is, in general, a fault.
    Samuel Taylor Coleridge (1772–1834)

    ... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.
    Adrienne Rich (b. 1929)