In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets. A graph may have many maximal independent sets of widely varying sizes; a largest maximal independent set is called a maximum independent set.
For example, in the graph P3, a path with three vertices a, b, and c, and two edges ab and bc, the sets {b} and {a,c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a,c}. In this same graph, the maximal cliques are the sets {a,b} and {b,c}.
The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids.
Read more about Maximal Independent Set: Related Vertex Sets, Graph Family Characterizations, Bounding The Number of Sets, Set Listing Algorithms
Famous quotes containing the words independent and/or set:
“A wise parent humours the desire for independent action, so as to become the friend and advisor when his absolute rule shall cease.”
—Elizabeth Gaskell (1810–1865)
“This is the Scroll of Thoth. Herein are set down the magic words by which Isis raised Osiris from the dead. Oh! Amon-Ra—Oh! God of Gods—Death is but the doorway to new life—We live today-we shall live again—In many forms shall we return-Oh, mighty one.”
—John L. Balderston (1899–1954)