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 \(G = (V, E)\) is a node subset \(D\) of \(V\) such that every node not in \(D\) is adjacent to at least one member of \(D\) [R242].
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
Notes
This function is an implementation of algorithm 7 in [R243] which finds some dominating set, not necessarily the smallest one.
References
[R242] (1, 2) http://en.wikipedia.org/wiki/Dominating_set [R243] (1, 2) AbdolHossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf