IndependenceNumber returns the independence number of the graph G.

MaximumIndependentSet returns a list of vertices comprising a maximum independent set of G.

Note a maximum independent set for G is necessarily also a minimum dominating set for G.

An independent set of a graph G is a subset S of the vertices of G, with the condition that if any vertices v1 and v2 are both members of S, the graph G must not contain an edge between them. An independent set of G is a clique of the complement of G.

A maximum independent set of G is an independent set of maximum size for the graph G.

The independence number of G is the cardinality of a maximum independent set of G. This is equal to the clique number of the complement of G.

The problem of finding a maximum independent set for a graph is NP-complete, meaning that no polynomial-time algorithm is presently known. The exhaustive search will take an exponential time on some graphs. For a faster algorithm that usually, but not always, returns a relatively large independent set see GreedyIndependentSet. This algorithm can also be selected by using the method = greedy option. The default is method = exact.

The strategy for MaximumIndependentSet and IndependenceNumber is a branch-and-bound backtracking algorithm using the greedy color bound (see Kreher and Stinson, 1999).

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$G≔\mathrm{CompleteGraph}\left(3\,4\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 7\; vertices\; and\; 12\; edge(s)}$

$\mathrm{DrawGraph}\left(G\right)$

$\mathrm{IndependenceNumber}\left(G\right)$

$4$

$\mathrm{MaximumIndependentSet}\left(G\right)$

$\left[4\,5\,6\,7\right]$

$C≔\mathrm{GraphComplement}\left(G\right)\:$

$\mathrm{DrawGraph}\left(C\right)$

$\mathrm{CliqueNumber}\left(C\right)$

$4$

$\mathrm{MaximumClique}\left(C\right)$

$\left[4\,5\,6\,7\right]$

$\mathrm{IndependenceNumber}\left(G\,'\mathrm{method}'='\mathrm{greedy}'\right)$

$4$

$\mathrm{MaximumIndependentSet}\left(G\,'\mathrm{method}'='\mathrm{greedy}'\right)$

$\left[4\,5\,6\,7\right]$

The GraphTheory[IndependenceNumber] and GraphTheory[MaximumIndependentSet] commands were updated in Maple 2019.

The method option was introduced in Maple 2019.

For more information on Maple 2019 changes, see Updates in Maple 2019.