Fractional strong matching preclusion for DHcube. (English) Zbl 1490.05223
Summary: Let \(F\) be a set edges and \(F^\prime\) be a set of edges and/or vertices of a graph \(G\), then \(F\) (resp. \( F^\prime \)) is a fractional matching preclusion set (resp. fractional strong matching preclusion set) if \(G-F\) (resp. \(G- F^\prime \)) contains no fractional perfect matching. The fractional matching preclusion number (resp. fractional strong matching preclusion number) of \(G\) is the minimum size of fractional matching preclusion set (resp. fractional strong matching preclusion set) of \(G\). In this paper, we obtain the fractional matching preclusion number and fractional strong matching preclusion number of the DHcube \(\operatorname{DH}(m,d,n)\) for \(n\geq 3\). In addition, all the optimal fractional matching preclusion sets and fractional strong matching preclusion sets of these graphs are categorized.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Birgham, R. C., Harry, F., Biolin, E. C., Yellen, J., Perfect matching preclusion, Congressus Numerantium174 (2005) 185-192. · Zbl 1091.05057 |
| [2] | Cheng, E., Lipták, L., Matching preclusion for some interconnection networks, Networks50 (2007) 173-180. · Zbl 1123.05073 |
| [3] | Cheng, E., Lensik, L., Lipman, M., Lipták, L., Matching preclusion for alternating group graphs and their generalizations, Int. J. Found. Comp. Sci.19 (2008) 1413-1437. · Zbl 1175.68287 |
| [4] | Cheng, E., Lensik, L., Lipman, M., Lipták, L., Conditional Matching preclusion sets, Inf. Sci.179 (2009) 1092-1101. · Zbl 1221.05265 |
| [5] | Ma, T., Mao, Y., Cheng, E., Wang, J., Fractional matching preclusion for (n, k)-star graphs, Parall. Process. Lett.28 (2018) 1850017. · Zbl 1492.05131 |
| [6] | Lv, H., Li, X., Zhang, H., Matching preclusion for balanced hypercubes, Theor. Comput. Sci.465 (2012) 10-20. · Zbl 1254.68188 |
| [7] | Hwo, J.-S., Lakshmivarahan, S., Dhall, S. K., A new class of interconnection networks based on the alternating group, Networks23 (1993) 315-326. · Zbl 0774.90031 |
| [8] | Park, J.-H., Ihm, I., Strong matching preclusion, Theor. Comput. Sci.412 (2011) 6409-6419. · Zbl 1232.05186 |
| [9] | Liu, Y., Liu, W., Fractional matching preclusion of graphs, J. Comb. Optim.34 (2016) 522-533. · Zbl 1376.05123 |
| [10] | Ma, T., Mao, Y., Cheng, E., Melekian, C., Fractional matching preclusion for (burnt) pancake graphs, International Symposium on Pervasive Systems, Algorithms and Networks, 2018. |
| [11] | Garey, M. R., Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (United States of America, 1979). · Zbl 0411.68039 |
| [12] | Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms9 (1982) 426-444. · Zbl 0651.68054 |
| [13] | Hung, R. W., DVcube: A novel compound architecture of disc-ring graph and hypercube-like graph, Theor. Comput. Sci.498 (2013) 28-45. · Zbl 1296.68014 |
| [14] | Vaidya, A. S., Rao, P. S. N., Shankar, S. R., A class of hypercube-like networks, in Proc. of the 5th IEEE Symposium on Parallel and Distributed Processing (SPDP), 1993, pp. 800-803. |
| [15] | Ma, T., Mao, Y., Cheng, E., Wang, J., Fractional matching preclusion for arrangement graphs, Discrete Appl. Math.270 (2019) 181-189. · Zbl 1426.05138 |
| [16] | Efe, K., The crossed cube architecture for parallel computing, IEEE Trans. Parallel Distrib. Syst.3 (1992) 513-524. |
| [17] | Hilbers, P. A. J., Koopman, M. R. J., van de Snepscheut, J. L. A., The twisted cube, PARLE: Parallel Architectures and Languages Europe, Volume 1: Parallel Architectures (1987), pp. 152-159. |
| [18] | Efe, K., A variation on the hypercube with lower diameter, IEEE Trans. Comput.40 (1991) 1312-1316. |
| [19] | Cull, P., Larson, S., The Möbius cubes, IEEE Trans. Comput.44 (1995) 647-659. · Zbl 1041.68522 |
| [20] | Singhvi, N. K., Ghose, K., The Mcube: A symmetrical cube based network with twisted links, in Proc. of the 9th IEEE International Parallel Processing Symposium (IPPS), 1995, pp. 11-16. |
| [21] | Guo, D., Chen, H., He, Y., Jin, H., Chen, C., Chen, H., Shu, Z., Huang, G., KCube: A novel architecture for interconnection networks, Inform. Process. Lett.110 (2010) 821-825. · Zbl 1234.68025 |
| [22] | Qin, X., Hao, R., Hamiltonian properties of some compound networks, Discrete Appl. Math.239 (2018) 174-182. · Zbl 1382.05040 |
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.
