dominating_set¶
- 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 [1].
- Parameters
- GNetworkX graph
- start_withnode (default=None)
Node to use as a starting point for the algorithm.
- Returns
- Dset
A dominating set for G.
See also
Notes
This function is an implementation of algorithm 7 in [2] which finds some dominating set, not necessarily the smallest one.
References
- 1
- 2
Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf