Graph Family Characterizations
Certain graph families have also been characterized in terms of their maximal cliques or maximal independent sets. Examples include the maximal-clique irreducible and hereditary maximal-clique irreducible graphs. A graph is said to be maximal-clique irreducible if every maximal clique has an edge that belongs to no other maximal clique, and hereditary maximal-clique irreducible if the same property is true for every induced subgraph. Hereditary maximal-clique irreducible graphs include triangle-free graphs, bipartite graphs, and interval graphs.
Cographs can be characterized as graphs in which every maximal clique intersects every maximal independent set, and in which the same property is true in all induced subgraphs.
Read more about this topic: Maximal Independent Set
Famous quotes containing the words graph and/or family:
“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)
“The law is equal before all of us; but we are not all equal before the law. Virtually there is one law for the rich and another for the poor, one law for the cunning and another for the simple, one law for the forceful and another for the feeble, one law for the ignorant and another for the learned, one law for the brave and another for the timid, and within family limits one law for the parent and no law at all for the child.”
—George Bernard Shaw (1856–1950)