摘要
一个图G的条件匹配排除数是最少的边的数量,使得删去这些边后形成的图既没有孤立点也没有完美匹配和几乎完美匹配.任何一个这样的边集称为G的一个最优条件匹配排除集.条件匹配排除数是衡量网络在边故障情况下的鲁棒性的参数之一.主要给出了修正泡型图的条件匹配排除数是2n-2(n≥5).
The conditional matching preclusion number of a graph is the minimum number of edges,whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings.Any such optimal set is called an optimally conditional matching preclusion set.The conditional matching preclusion number is one of the parameters to measure the robustness of interconnection networks in the event of edge failure.In this paper,we work out that the conditional matching preclusion number of the modified bubble sort graph is 2n-2(n≥5).
作者
王世英
杨婕
马晓蕾
Wang Shiying;Yang Jie;Ma Xiaolei(College of Mathematics and Information Science,Henan Normal University,Xinxiang 453007,China)
出处
《河南师范大学学报（自然科学版）》
CAS
北大核心
2021年第1期1-9,F0002,共10页
Journal of Henan Normal University(Natural Science Edition)
基金
国家自然科学基金(61772010)。
关键词
CAYLEY图
修正泡型图
匹配
条件匹配排除
Cayley graphs
modified bubble sort graphs
matchings
conditional matching preclusion
