Integer \(k\)-matching preclusion of twisted cubes and \((n,s)\)-star graphs. (English) Zbl 1511.05192
Summary: An integer \(k\)-matching of a graph \(G\) is a function \(f\) from \(E(G)\) to \(\{0,1,\cdots, k\}\) such that the sum of \(f(e)\) is not more than \(k\) for any vertex \(u\), where the sum is taken over all edges \(e\) incident to \(u\). When \(k=1\), the integer \(k\)-matching is a matching. The (strong) integer \(k\)-matching preclusion number of \(G\), denoted by \(mp^k (G) (smp^k (G))\), is the minimum number of edges (vertices and edges) whose deletion results in a graph with neither perfect integer \(k\)-matching nor almost perfect integer \(k\)-matching. This is an extension of the (strong) matching preclusion problem that was introduced by R. C. Brigham et al. [Congr. Numerantium 174, 185–192 (2005; Zbl 1091.05057)] and J.-H. Park and I. Ihm [Theor. Comput. Sci. 412, No. 45, 6409–6419 (2011; Zbl 1232.05186)]. The twisted cubes and the \((n,s)\)-star graphs have more desirable properties. In this paper, \(MP^k\) number and \(SMP^k\) number of the twisted cubes and \((n,s)\)-star graphs are given, respectively.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C72 | Fractional graph theory, fuzzy graph theory |
Keywords:
integer \(k\)-matching; (strong) integer \(k\)-matching preclusion; number; twisted cube; \((n,s)\)-star graphReferences:
| [1] | Liu, Y.; Su, X.; Xiong, D., Integer \(k\)-matchings of graphs: \(k\)-berge-tutte formula, \(k\)-factor-critical graphs and \(k\)-barriers, Disc. Appl. Math., 297, 120-128 (2021) · Zbl 1462.05303 |
| [2] | Brigham, R.; Harary, F.; Violin, E.; Yellen, J., Perfect-matching preclusion, Congr. Numer., 174, 185-192 (2005) · Zbl 1091.05057 |
| [3] | Park, J.; Ihm, I., Strong matching preclusion, Theor. Comput. Sci., 412, 45, 6409-6419 (2011) · Zbl 1232.05186 |
| [4] | Liu, Y.; Liu, W., Fractional matching preclusion of graphs, J. Combin. Optim., 34, 2, 522-533 (2017) · Zbl 1376.05123 |
| [5] | Liu, Y.; Liu, X., Integer \(k\)-matchings of graphs, Disc. Appl. Math., 235, 118-128 (2018) · Zbl 1375.05218 |
| [6] | 1850017 · Zbl 1492.05131 |
| [7] | Bhaskar, R.; Cheng, E.; Liang, M.; Pandey, S., Matching preclusion and conditional matching preclusion problems for twisted cubes, Congr. Numer., 205, 175-185 (2010) · Zbl 1231.05209 |
| [8] | Huang, W.; Tan, J.; Hung, C., Fault-tolerant hamiltonicity of twisted cubes, J. Paral. and Distr. Comput., 62, 591-604 (2002) · Zbl 1008.68017 |
| [9] | C. Chang, Y. Liu, Integer \(k\)-matching preclusion of arrangement graphs, 2021. Submitted. |
| [10] | Fu, J., Conditional fault hamiltonicity of the complete graph, Inform. Process. Lett., 107, 3, 110-113 (2008) · Zbl 1185.05094 |
| [11] | Cheng, E.; Kelm, J.; Renzi, J., Strong matching preclusion of \(( n , k )\)-star graphs, Theor. Comput. Sci., 615, 91-101 (2016) · Zbl 1334.05115 |
| [12] | Hsu, H.; Hsieh, Y.; Jimmy, J.; Hsu, L., Fault hamiltonicity and fault hamiltonian connectivity of the \(n , s\)-star graphs, Networks., 42, 4, 189-201 (2003) · Zbl 1031.05079 |
| [13] | Akers, S.; Harel, D.; Krishnamurthy, B., The star graph: An attractive alternative to the \(n\)-cube, Proc. Int. Conf. on Paral. Proce., 393-400 (1987) |
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.
