8.6.1. networkx.algorithms.dominating.dominating_set¶

networkx.algorithms.dominating.dominating_set(G, start_with=None)[source]¶

Finds a dominating set for the graph G.

A dominating set for a graph with node set V is a subset D of V such that every node not in D is adjacent to at least one member of D [R649].

Parameters:	G : NetworkX graph start_with : node (default=None) Node to use as a starting point for the algorithm.
Returns:	D : set A dominating set for G.

See also

is_dominating_set

Notes

This function is an implementation of algorithm 7 in [R650] which finds some dominating set, not necessarily the smallest one.

References

[R649]

(1, 2) http://en.wikipedia.org/wiki/Dominating_set

[R650]

(1, 2) Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf