Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

dominating_set¶

dominating_set(G, start_with=None)[source]

Finds a dominating set for the graph G.

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

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

Notes

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

References

 [2] Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf