Scaling of Minimum Dominating Sets in Various Scale-Free Network Ensembles

We study the scaling behavior of the size of minimum dominating sets (MDS) in scale-free networks, with respect to network size $N$ and power-law exponent $\gamma $ [Nacher et al., NJP 073005 (2012)]. Network samples are constructed by either the configuration model (CM) via multigraphs, or exact degree sequence sampling methods. The MDS is found by a sequential greedy algorithm. We control the average degree by setting an appropriate lower degree cutoff $k_{\min } $. Two subtypes of networks are studied according to the maximum degree cutoff $k_{\max } $. Our results show that when $k_{\max } =\sqrt N $ all networks have similar scaling. The size of MDS is linear with respect to $N$, and for a given $N$, it increases for low $\gamma $ values. When $k_{\max } =N-1$, we find a structural difference between CM networks, and networks constructed by exact sampling methods. For the latter, we find a scaling transition of the MDS size from O(N) to O(1) at approximately $\gamma \approx 1.9$, due to the appearance of star subgraphs with O(N) central degree. For a given $N$, the size of MDS increases for higher $\gamma $ values. However, in CM networks the MDS scales linearly with $N$, and for a given $N$, it is non-monotonic with respect to $\gamma $. Finally, we find that a partial MDS, which dominates only a certain fraction of the network, has the same scaling as full domination, even for as low as $30\% $ dominated fraction.