摘要
一个图的条件匹配排除数是最少的边的数量,使得删除这些边形成的图既没有孤立点,也没有完美匹配和几乎完美匹配.本文给出了泡型图的条件匹配排除数和它的所有最优集.
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.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.In this paper,we give the conditional matching preclusion number and all optimal sets for the bubble sort graphs.
出处
《新疆大学学报（自然科学版）》
CAS
2011年第1期23-35,共13页
Journal of Xinjiang University(Natural Science Edition)
基金
国家自然科学基金资助项目(61070229)
关键词
完美匹配
泡型图
条件匹配排除
perfect matchings
bubble sort graphs
conditional matching preclusion
