×

Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket. (English) Zbl 1481.05121

Summary: 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ński 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ński gasket. Moreover, the number of all MEDSs in the pseudofractal scale-free web is also less than that corresponding to the Sierpiński gasket. We argue that the difference of the size and number of MEDSs between the two studied graphs lies in the scale-free topology.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
28A80 Fractals
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Mitchell, S. and Hedetniemi, S., Edge domination in trees, in Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State University, Baton Rouge, LA, 1977), pp. 489-509. · Zbl 0433.05023
[2] Papakostas, D., Eshghi, S., Katsaros, D. and Tassiulas, L., Distributed algorithms for multi-layer connected edge dominating sets, IEEE Control Syst. Lett.3(1) (2019) 31-36.
[3] Butenko, S., Pardalos, P., Sergienko, I., Shylo, V. and Stetsyuk, P., Finding maximum independent sets in graphs arising from coding theory, in Proceedings of the 2002 ACM Symposium on Applied computing (ACM, 2002), pp. 542-546.
[4] Araujo, F., Farinha, J., Domingues, P., Silaghi, G. C. and Kondo, D., A maximum independent set approach for collusion detection in voting pools, J. Parallel Distrib. Comput.71(10) (2011) 1356-1366.
[5] Joo, C., Lin, X., Ryu, J. and Shroff, N. B., Distributed greedy approximation to maximum weighted independent set for scheduling with fading channels, IEEE/ACM Trans. Netw.24(3) (2016) 1476-1488.
[6] Cardinal, J., Langerman, S. and Levy, E., Improved approximation bounds for edge dominating set in dense graphs, Theoret. Comput. Sci.410(8-10) (2009) 949-957. · Zbl 1165.68055
[7] Schmied, R. and Viehmann, C., Approximating edge dominating set in dense graphs, Theoret. Comput. Sci.414(1) (2012) 92-99. · Zbl 1235.68079
[8] Xiao, M. and Nagamochi, H., Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs, Theoret. Comput. Sci.469 (2013) 92-104. · Zbl 1259.68263
[9] Xiao, M. and Nagamochi, H., A refined exact algorithm for edge dominating set, Theoret. Comput. Sci.560 (2014) 207-216. · Zbl 1304.05142
[10] Escoffier, B., Monnot, J., Paschos, V. T. and Xiao, M., New results on polynomial inapproximabilityand fixed parameter approximability of edge dominating set, Theory Comput. Syst.56(2) (2015) 330-346. · Zbl 1328.68090
[11] Golovach, P. A., Heggernes, P., Kratsch, D. and Villanger, Y., An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, Algorithmica72(3) (2015) 836-859. · Zbl 1330.05118
[12] Fujito, T. and Shimoda, T., On approximating (connected) 2-edge dominating set by a tree, Theory Comput. Syst.62(3) (2018) 533-556. · Zbl 1390.68762
[13] Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y. and Okamoto, Y., Minimum-cost b-edge dominating sets on trees, Algorithmica81(1) (2019) 343-366. · Zbl 1410.68168
[14] Yannakakis, M. and Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math.38(3) (1980) 364-372. · Zbl 0455.05047
[15] Valiant, L., The complexity of computing the permanent, Theor. Comput. Sci.8(2) (1979) 189-201. · Zbl 0415.68008
[16] Valiant, L., The complexity of enumeration and reliability problems, SIAM J. Comput.8(3) (1979) 410-421. · Zbl 0419.68082
[17] Wang, J., Yang, Y., Guo, J. and Chen, J., Planar graph vertex partition for linear problem kernels, J. Comput. Syst. Sci.79(5) (2013) 609-621. · Zbl 1268.68136
[18] Lovász, L. and Plummer, M. D., Matching Theory, , Vol. 29 (North Holland, New York, 1986). · Zbl 0618.05001
[19] Newman, M. E. J., The structure and function of complex networks, SIAM Rev.45(2) (2003) 167-256. · Zbl 1029.68010
[20] Barabási, A. and Albert, R., Emergence of scaling in random networks, Science286(5439) (1999) 509-512. · Zbl 1226.05223
[21] Chung, F. and Lu, L., The average distances in random graphs with given expected degrees, Proc. Natl. Acad. Sci. USA99(25) (2002) 15879-15882. · Zbl 1064.05137
[22] Liu, Y.-Y., Slotine, J.-J. and Barabási, A.-L., Controllability of complex networks, Nature473(7346) (2011) 167-173.
[23] Zhang, Z. and Wu, B., Pfaffian orientations and perfect matchings of scale-free networks, Theoret. Comput. Sci.570 (2015) 55-69. · Zbl 1306.05198
[24] Gast, M., Hauptmann, M. and Karpinski, M., Inapproximability of dominating set on power law graphs, Theoret. Comput. Sci.562 (2015) 436-452. · Zbl 1305.05174
[25] Jin, Y., Li, H. and Zhang, Z., Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs, Theoret. Comput. Sci.703 (2017) 37-54. · Zbl 1380.05182
[26] Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J. and Faloutsos, C., Epidemic thresholds in real networks, ACM Trans. Inform. Syst. Secur.10(4) (2008) 13.
[27] Yi, Y., Zhang, Z. and Patterson, S., Scale-free loopy structure is resistant to noise in consensus dynamics in power-law graphs, IEEE Trans. Cybern.50(1) (2020) 190-200.
[28] Dorogovtsev, S. N., Goltsev, A. V. and Mendes, J. F. F., Pseudofractal scale-free web, Phys. Rev. E65(6) (2002) 066122.
[29] Fukushima, M. and Shima, T., On a spectral analysis for the Sierpiński gasket, Potential Anal.1(1) (1992) 1-35. · Zbl 1081.31501
[30] Shang, J., Wang, Y., Chen, M., Dai, J., Zhou, X., Kuttner, J., Hilt, G., Shao, X., Gottfried, J. M. and Wu, K., Assembling molecular Sierpiński triangle fractals, Nat. Chem.7(5) (2015) 389.
[31] Mo, Y., Chen, T., Dai, J., Wu, K. and Wang, D., On-surface synthesis of highly ordered covalent Sierpiński triangle fractals, J. Am. Chem. Soc.141(29) (2019) 11378-11382.
[32] Jiang, Z., Liu, D., Chen, M., Wang, J., Zhao, H., Li, Y., Zhang, Z., Xie, T., Wang, F., Li, X.et al., Assembling shape-persistent high-order Sierpiński triangular fractals, iScience23(5) (2020) 101064.
[33] Lathrop, J. I., Lutz, J. H. and Summers, S. M., Strict self-assembly of discrete Sierpiński triangles, Theoret. Comput. Sci.410(4-5) (2009) 384-405. · Zbl 1160.68012
[34] Ettestad, D. and Carbonara, J., The Sierpiński triangle plane, Fractals26(1) (2018) 1850003. · Zbl 1432.28004
[35] Ettestad, D. and Carbonara, J., Distinguishing between Sierpiński triangle constructions, Fractals27(5) (2019) 1950091. · Zbl 1434.28019
[36] Qi, Y. and Zhang, Z., Spectral properties of extended Sierpiński graphs and their applications, IEEE Trans. Netw. Sci. Eng.6(3) (2019) 512-522.
[37] Qi, Y., Dong, Y., Zhang, Z. and Zhang, Z., Hitting times for random walks on Sierpiński graphs and hierarchical graphs, Comput. J.63(9) (2020) 1385-1396.
[38] Cheng, K., Chen, D., Xue, Y. and Zhang, Q., The scale-free and small-world properties of complex networks on Sierpiński-type hexagon, Fractals28(3) (2020) 2050054. · Zbl 1434.28013
[39] Wu, Y., Chen, Z., Zhang, X. and Zhao, X., Mean value property of harmonic function on the higher-dimensional Sierpiński gasket, Fractals28(5) (2020) 2050077. · Zbl 1445.28016
[40] Kneževic, M. and Vannimenus, J., Large-scale properties and collapse transition of branched polymers: Exact results on fractal lattices, Phys. Rev. Lett.56(15) (1986) 1591.
[41] Zhang, Z. Z., Zhou, S. G. and Chen, L. C., Evolving pseudofractal networks, Eur. Phys. J. B58(3) (2007) 337-344.
[42] Song, C., Havlin, S. and Makse, H., Self-similarity of complex networks, Nature433(7024) (2005) 392-395.
[43] Xie, P., Zhang, Z. and Comellas, F., On the spectrum of the normalized Laplacian of iterated triangulations of graphs, Appl. Math. Comput.273 (2016) 1123-1129. · Zbl 1410.05143
[44] Xie, P., Zhang, Z. and Comellas, F., The normalized Laplacian spectrum of subdivisions of a graph, Appl. Math. Comput.286 (2016) 250-256. · Zbl 1410.05144
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.