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)
“Notwithstanding the unaccountable apathy with which of late years the Indians have been sometimes abandoned to their enemies, it is not to be doubted that it is the good pleasure and the understanding of all humane persons in the Republic, of the men and the matrons sitting in the thriving independent families all over the land, that they shall be duly cared for; that they shall taste justice and love from all to whom we have delegated the office of dealing with them.”
—Ralph Waldo Emerson (1803–1882)