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\) [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:	set

Notes

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

See also

is_dominating_set()

References

[1]	http://en.wikipedia.org/wiki/Dominating_set

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