Induced Path - Characterization of Graph Families

Characterization of Graph Families

Many important graph families can be characterized in terms of the induced paths or cycles of the graphs in the family.

  • Trivially, the connected graphs with no induced path of length two are the complete graphs, and the connected graphs with no induced cycle are the trees.
  • A triangle-free graph is a graph with no induced cycle of length three.
  • The cographs are exactly the graphs with no induced path of length three.
  • The chordal graphs are the graphs with no induced cycle of length four or more.
  • The even-hole-free graphs are the graphs in containing no induced cycles with an even number of vertices.
  • The trivially perfect graphs are the graphs that have neither an induced path of length three nor an induced cycle of length four.
  • By the strong perfect graph theorem, the perfect graphs are the graphs with no odd hole and no odd antihole.
  • The distance-hereditary graphs are the graphs in which every induced path is a shortest path, and the graphs in which every two induced paths between the same two vertices have the same length.
  • The block graphs are the graphs in which there is at most one induced path between any two vertices, and the connected block graphs are the graphs in which there is exactly one induced path between every two vertices.

Read more about this topic:  Induced Path

Famous quotes containing the words graph and/or families:

    “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)

    “We urgently need a debate about the best ways of supporting families in modern America, without blinders that prevent us from seeing the full extent of dependence and interdependence in American life. As long as we pretend that only poor or abnormal families need outside assistance, we will shortchange poor families, overcompensate rich ones, and fail to come up with effective policies for helping families in the middle.”
    —Stephanie Coontz (20th century)