IsDominatingSet(G, S) returns true if the collection of vertices S is a dominating set for G, and returns false otherwise.

IsIndependentSet(G, S) returns true if the collection of vertices S represents an independent set in G, and returns false otherwise.

To find a minimum dominating set or a maximum independent set for G, use MaximumIndependentSet.

A dominating set of a graph G is a subset S of the vertices of G, with the condition that every vertex in G must either be an element of S or the neighbor of an element of S.

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.

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

$G≔\mathrm{PathGraph}\left(5\right)$

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

$\mathrm{S1}≔\left\{1\,2\,3\,4\,5\right\}$

$\mathrm{S1}≔\left\{1\,2\,3\,4\,5\right\}$

$\mathrm{IsDominatingSet}\left(G\,\mathrm{S1}\right)$

$\mathrm{true}$

$\mathrm{IsIndependentSet}\left(G\,\mathrm{S1}\right)$

$\mathrm{false}$

$\mathrm{S2}≔\left\{1\,3\right\}$

$\mathrm{S2}≔\left\{1\,3\right\}$

$\mathrm{IsDominatingSet}\left(G\,\mathrm{S2}\right)$

$\mathrm{false}$

$\mathrm{IsIndependentSet}\left(G\,\mathrm{S2}\right)$

$\mathrm{true}$

$\mathrm{S3}≔\left\{1\,3\,5\right\}$

$\mathrm{S3}≔\left\{1\,3\,5\right\}$

$\mathrm{IsDominatingSet}\left(G\,\mathrm{S3}\right)$

$\mathrm{true}$

$\mathrm{IsIndependentSet}\left(G\,\mathrm{S3}\right)$

$\mathrm{true}$

The GraphTheory[IsDominatingSet] and GraphTheory[IsIndependentSet] commands were introduced in Maple 2024.

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