grinpy.invariants.domination.min_dominating_set¶
-
grinpy.invariants.domination.
min_dominating_set
(G)¶ Return a smallest dominating set in the graph.
The method to compute the set is brute force except that the subsets searched begin with those whose cardinality is equal to the sub-domination number of the graph, which was defined by Amos et al. and shown to be a tractable lower bound for the k-domination number.
Parameters: - G (NetworkX graph) – An undirected graph.
- k (int) – A positive integer.
Returns: A list of nodes in a smallest dominating set in the graph.
Return type: list
See also
References
D. Amos, J. Asplund, B. Brimkov and R. Davila, The sub-k-domination number of a graph with applications to k-domination, arXiv preprint arXiv:1611.02379, (2016)