IsDominatingSet - Maple Help

GraphTheory

 IsDominatingSet
 test whether set is dominating set for graph
 IsIndependentSet
 test whether set is independent set for graph

 Calling Sequence IsDominatingSet(G,S) IsIndependentSet(G, S)

Parameters

 G - undirected graph S - (optional) list or set of vertices

Description

 • 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.

Definitions

 • 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.

Examples

 > $\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\left(s\right)}}$ (1)
 > $\mathrm{S1}≔\left\{1,2,3,4,5\right\}$
 ${\mathrm{S1}}{≔}\left\{{1}{,}{2}{,}{3}{,}{4}{,}{5}\right\}$ (2)
 > $\mathrm{IsDominatingSet}\left(G,\mathrm{S1}\right)$
 ${\mathrm{true}}$ (3)
 > $\mathrm{IsIndependentSet}\left(G,\mathrm{S1}\right)$
 ${\mathrm{false}}$ (4)
 > $\mathrm{S2}≔\left\{1,3\right\}$
 ${\mathrm{S2}}{≔}\left\{{1}{,}{3}\right\}$ (5)
 > $\mathrm{IsDominatingSet}\left(G,\mathrm{S2}\right)$
 ${\mathrm{false}}$ (6)
 > $\mathrm{IsIndependentSet}\left(G,\mathrm{S2}\right)$
 ${\mathrm{true}}$ (7)
 > $\mathrm{S3}≔\left\{1,3,5\right\}$
 ${\mathrm{S3}}{≔}\left\{{1}{,}{3}{,}{5}\right\}$ (8)
 > $\mathrm{IsDominatingSet}\left(G,\mathrm{S3}\right)$
 ${\mathrm{true}}$ (9)
 > $\mathrm{IsIndependentSet}\left(G,\mathrm{S3}\right)$
 ${\mathrm{true}}$ (10)

Compatibility

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