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:
“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)
“In families children tend to take on stock roles, as if there were hats hung up in some secret place, visible only to the children. Each succeeding child selects a hat and takes on that role: the good child, the black sheep, the clown, and so forth.”
—Ellen Galinsky (20th century)