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.
Returns: D – A dominating set for G.
Return type: Notes
This function is an implementation of algorithm 7 in [2] which finds some dominating set, not necessarily the smallest one.
See also
References
[1] http://en.wikipedia.org/wiki/Dominating_set [2] AbdolHossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf