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)
“Affection, indulgence, and humor alike are powerless against the instinct of children to rebel. It is essential to their minds and their wills as exercise is to their bodies. If they have no reasons, they will invent them, like nations bound on war. It is hard to imagine families limp enough always to be at peace. Wherever there is character there will be conflict. The best that children and parents can hope for is that the wounds of their conflict may not be too deep or too lasting.”
—New York State Division of Youth Newsletter (20th century)