Skip to main content
`Ctrl`+`K`

# dominating_set

dominating_set(G, start_with=None)

  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:
    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

  `is_dominating_set`

  Notes

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

  References

  [1]

  https://en.wikipedia.org/wiki/Dominating_set

  [2]

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