Klein瓶上达到最大因子临界度的图的刻画

摘要

若从一个阶数为n的图中任意删除p(p＜n)个点之后都有完美匹配,则称此图是p-因子临界的.给定曲面∑,令p(∑)为最小的正整数满足此曲面上的图都不是p(∑)-因子临界的.文献[9]证明了p(N2)=6,其中N2代表曲面Klein瓶.即Klein瓶上的图最多是5-因子临界的,刻画了Klein瓶上所有5-因子临界图.%A graph of order n is said to be p-factor-critical for non-negative integer p＜n if the removal of any p vertices results in a graph with a perfect matching.For an arbitrary surface ∑,let p(∑) denote the smallest integer such that no graph in ∑ is p(∑)-factor-critical.We call p(∑) the factor-criticality of surface ∑.Reference [9] has shown thatp(N2)=6 for the Klein bottle N2.That is,graphs on the Klein-bottle are at most 5-factor-critical.The paper is to characterize all 5-factor-critical graphs on the Klein bottle.