Edge Domination Number and the Number of Minimum Edge Dominating Sets in Pseudofractal Scale-Free Web and Sierpiński Gasket

Xiaotian Zhou, Zhongzhi ZhangarXiv 2021 · DOI · OpenReview

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 recursive construction of $G_{n+1}$ from three replicas of $G_n$.

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:

  1. Pseudofractal Scale-Free Web: A heterogeneous network where vertex degrees follow a power-law distribution, characterized by high-degree "hubs."
  2. Sierpiński Gasket: A homogeneous fractal network where almost all vertices have a degree of 4.
Iterative construction of the Sierpiński gasket for generations $n=1, 2, 3$.

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

Abstract

As a fundamental research object, the minimum edge dominating set (MEDS) problem is of both theoretical and practical interest. However, determining the size of a MEDS and the number of all MEDSs in a general graph is NP-hard, and it thus makes sense to find special graphs for which the MEDS problem can be exactly solved. In this paper, we study analytically the MEDS problem in the pseudofractal scale-free web and the Sierpi\'nski gasket with the same number of vertices and edges. For both graphs, we obtain exact expressions for the edge domination number, as well as recursive solutions to the number of distinct MEDSs. In the pseudofractal scale-free web, the edge domination number is one-ninth of the number of edges, which is three-fifths of the edge domination number of the Sierpi\'nski gasket. Moreover, the number of all MEDSs in the pseudofractal scale-free web is also less than that corresponding to the Sierpi\'nski gasket. We argue that the difference of the size and number of MEDSs between the two studied graphs lies in the scale-free topology.
BibTeX
@misc{zhou2021edge,
  author = {Xiaotian Zhou and Zhongzhi Zhang},
  title = {{Edge Domination Number and the Number of Minimum Edge Dominating Sets in Pseudofractal Scale-Free Web and Sierpiński Gasket}},
  year = {2021},
  eprint = {2106.05808},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.05808},
}
Figure