|
n维扭曲立方体是超k-匹配图
|
Abstract:
图 的整数 -匹配是由 到 上的映射 ,满足对任意点 ,所有 的加和不超过 ,其中 之和为所有以点 为端点的边 。当 时,整数 -匹配即为匹配。(强)整数 -匹配排除数由 表示,是被一个图删去后该图既不存在完美整数 -匹配,也不存在几乎完美整数 -匹配的最小点集(点集与边集)的元素数。Caibing Chang、Xianfu Li and Yan Liu介绍了 。本文提出超强整数 -匹配的定义并证明
[1] | Cheng, E. and Lipták, L. (2007) Matching Preclusion for Some Interconnection Networks. Networks, 50, 173-180. https://doi.org/10.1002/net.20187 |
[2] | Cheng, E., Lesniak, L., Lipman, M.J. and Lipták, L. (2008) Matching Preclusion for Alternating Group Graphs and Their Generalizations. International Journal of Foundations of Computer Science, 19, 1413-1437. https://doi.org/10.1142/s0129054108006364 |
[3] | Cheng, E., Lesniak, L., Lipman, M.J. and Lipták, L. (2009) Conditional Matching Preclusion Sets. Information Sciences, 179, 1092-1101. https://doi.org/10.1016/j.ins.2008.10.029 |
[4] | Chang, C., Li, X. and Liu, Y. (2023) Integer k-Matching Preclusion of Twisted Cubes and (n, s)-Star Graphs. Applied Mathematics and Computation, 440, Article ID: 127638. https://doi.org/10.1016/j.amc.2022.127638 |
[5] | Brigham, R.C., Harary, F., Violin, E.C., et al. (2005) Perfect-Matching Preclusion. Congressus Numerantium, 174, Article 42. |
[6] | Liu, Y., Su, X. and Xiong, D. (2021) Integer k-Matchings of Graphs: k-Berge-Tutte Formula, k-Factor-Critical Graphs and k-Barriers. Discrete Applied Mathematics, 297, 120-128. |
[7] | Liu, Y. and Liu, X. (2018) Integer k-Matchings of Graphs. Discrete Applied Mathematics, 235, 118-128. https://doi.org/10.1016/j.dam.2017.08.013 |