Abstract
Determining the size and count of minimum edge dominating sets (MEDS) is an NP-hard problem in general graphs. This paper provides exact analytical solutions for two specific complex networks: the pseudofractal scale-free web and the Sierpiński gasket. By exploiting their self-similar structures, we derive exact formulas for the edge domination number and recursive solutions for the number of MEDSs. Our results show that the scale-free web's edge domination number is only three-fifths of that for the Sierpiński gasket of equivalent size, highlighting how scale-free topology facilitates more efficient network domination.
Introduction
In graph theory, an Edge Dominating Set (EDS) is a subset of edges such that every edge in the graph is either in the set or adjacent to at least one edge in the set. The Minimum Edge Dominating Set (MEDS) problem seeks the smallest such set. This problem has significant applications in network monitoring, scheduling, and coding theory. However, finding a MEDS is NP-hard, and counting all MEDSs is #P-complete. This study focuses on two deterministic fractal graphs—the pseudofractal scale-free web and the Sierpiński gasket—to understand how network topology, specifically scale-free properties, affects domination.
Methods: Decimation and Self-Similarity
The core of the analysis relies on the recursive construction of the studied graphs. Both the pseudofractal scale-free web and the Sierpiński gasket are built iteratively, allowing the problem to be broken down into smaller, manageable components.
The authors employ a decimation technique that leverages this self-similarity. They classify the "hub" or boundary vertices of the graphs into three distinct states:
- Filled (●): At least one incident edge is included in the dominating set.
- Empty (○): No incident edges are in the set, but all are dominated by other edges.
- Cross (⊗): No incident edges are in the set, and some remain undominated.
By analyzing how these states evolve and combine when merging smaller graph replicas into larger ones, the researchers established a system of recursive equations to calculate the size ($\gamma_n$) and the total number ($x_n$) of MEDSs.
Graph Models
The study compares two models with the same number of vertices and edges to isolate the effect of topology:
- Pseudofractal Scale-Free Web: A heterogeneous network where vertex degrees follow a power-law distribution, characterized by high-degree "hubs."
- Sierpiński Gasket: A homogeneous fractal network where almost all vertices have a degree of 4.
Key Results and Insights
The analytical results reveal a significant advantage for scale-free architectures in terms of domination efficiency:
- Edge Domination Number ($\gamma_n$):
- Scale-free web: $\gamma_n = 3^{n-2}$.
- Sierpiński gasket: $\gamma_n = 5 \cdot 3^{n-3}$.
- Comparison: The scale-free web requires only 60% (3/5) of the edges needed by the Sierpiński gasket to achieve full domination. In the scale-free web, the domination number is exactly one-ninth of the total edges.
- The Role of Hubs: In scale-free networks, high-degree hubs act as "super-connectors." Selecting an edge incident to a hub covers a disproportionately large number of adjacent edges simultaneously. In contrast, the homogeneous distribution of edges in the Sierpiński gasket requires more coverage points.
- Combinatorial Sparsity: The number of distinct MEDSs is also smaller in the scale-free web. This suggests that the optimal domination structure in scale-free networks is more "rigid" and constrained compared to the more flexible, but less efficient, homogeneous fractal.
Conclusion
This research provides the first exact solutions for the MEDS problem in scale-free and homogeneous fractal graphs. The findings demonstrate that scale-free topology significantly reduces the resources required for edge domination. These exact results serve as a valuable benchmark for testing approximation algorithms on large-scale complex networks and suggest that the decimation method can be extended to other graph-theoretical problems in self-similar structures.
Summary updated