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

The characterization of extremal factor-critical graphs on the Klein bottle

若从一个阶数为n的图中任意删除p(p<n)个点之后都有完美匹配,则称此图是p-因子临界的.给定曲面Σ,令p(Σ)为最小的正整数满足此曲面上的图都不是p(Σ)-因子临界的.文献[9]证明了p(N_2)=6,其中N_2代表曲面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 Z, let p（Z） denote the smallest integer such that no graph in Z is p（-r）- factor- critical. We call p（Z） the factor-criticality of surface Z. Reference [9] has shown that p（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.