Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
From MaRDI portal
(Redirected from Publication:526869)
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'nski 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'nski 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.
Recommendations
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
- Statistical mechanics of the minimum dominating set problem
- On maximum number of minimal dominating sets in graphs
- Algorithms and Models for the Web-Graph
Cites work
- A dominating-set-based routing scheme in ad hoc wireless networks
- Combinatorial bounds via measure and conquer
- Dominating sets in planar graphs
- Dominating sets in triangulations on surfaces
- Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
- Emergence of Scaling in Random Networks
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- Inapproximability of dominating set on power law graphs
- Matching theory
- On dominating sets of maximal outerplanar and planar graphs
- On the enumeration of minimal dominating sets and related notions
- On the number of minimal dominating sets on some graph classes
- Statistical mechanics of the minimum dominating set problem
- The Structure and Function of Complex Networks
Cited in
(11)- Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
- Combinatorial properties of Farey graphs
- Dominating problems in swapped networks
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
- Lazy random walks on pseudofractal scale-free web with a perfect trap
- Applications of Markov spectra for the weighted partition network by the substitution rule
- COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB
- Variants of the domination number for flower snarks
- Diagonal of pseudoinverse of graph Laplacian: fast estimation and exact results
- Statistical mechanics of the minimum dominating set problem
This page was built for publication: Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526869)
