Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph

Abstract

The minimum dominating set (MDS) problem is a fundamental subject of theoretical computer science, and has found vast applications in different areas, including sensor networks, protein interaction networks, and structural controllability. However, the determination of the size of a MDS and the number of all MDSs in a general network is NP-hard, and it thus makes sense to seek particular graphs for which the MDS problem can be solved analytically. In this paper, we study the MDS problem in the pseudofractal scale-free web and the Sierpiński graph, which have the same number of vertices and edges. For both networks, we determine explicitly the domination number, as well as the number of distinct MDSs. We show that the pseudofractal scale-free web has a unique MDS, and its domination number is only half of that for the Sierpiński graph, which has many MDSs. We argue that the scale-free topology is responsible for the difference of the size and number of MDSs between the two studied graphs, which in turn indicates that power-law degree distribution plays an important role in the MDS problem and its applications in scale-free networks.

References in corpus (11)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Self-similarity of complex networks
• Pseudofractal Scale-free Web
• Controlling edge dynamics in complex networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Enumeration of spanning trees in a pseudofractal scale-free web
• Evolving small-world scale-free networks consist of cliques
• Statistical Mechanics of the Minimum Dominating Set Problem
• Dominating Scale-Free Networks Using Generalized Probabilistic Methods
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs

Cited by in corpus (8)

• Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
• Stochastic and mixed flower graphs
• Coherence Scaling of Noisy Second-Order Scale-Free Consensus Networks
• Spectra, hitting times, and resistance distances of $q$-subdivision graphs
• Spanning Trees of Recursive Scale-Free Graphs
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web
• Some Combinatorial Problems in Power-law Graphs
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket