Related Vertex Sets
If S is a maximal independent set in some graph, it is a maximal clique or maximal complete subgraph in the complementary graph. A maximal clique is a set of vertices that induces a complete subgraph, and that is not a subset of the vertices of any larger complete subgraph. That is, it is a set S such that every pair of vertices in S is connected by an edge and every vertex not in S is missing an edge to at least one vertex in S. A graph may have many maximal cliques, of varying sizes; finding the largest of these is the maximum clique problem.
Some authors include maximality as part of the definition of a clique, and refer to maximal cliques simply as cliques.
The complement of a maximal independent set, that is, the set of vertices not belonging to the independent set, forms a minimal vertex cover. That is, the complement is a vertex cover, a set of vertices that includes at least one endpoint of each edge, and is minimal in the sense that none of its vertices can be removed while preserving the property that it is a cover. Minimal vertex covers have been studied in statistical mechanics in connection with the hard-sphere lattice gas model, a mathematical abstraction of fluid-solid state transitions.
Every maximal independent set is a dominating set, a set of vertices such that every vertex in the graph either belongs to the set or is adjacent to the set. A set of vertices is a maximal independent set if and only if it is an independent dominating set.
Read more about this topic: Maximal Independent Set
Famous quotes containing the words related and/or sets:
“One does not realize the historical sensation as a re-experiencing, but as an understanding that is closely related to the understanding of music, or rather of the world by means of music.”
—Johan Huizinga (1872–1945)
“The world can doubtless never be well known by theory: practice is absolutely necessary; but surely it is of great use to a young man, before he sets out for that country, full of mazes, windings, and turnings, to have at least a general map of it, made by some experienced traveller.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)