关于3-点临界图的一个猜想的证明

A conjecture on 3-vertex-critical graphs

设γ(G)是图G的点控制数.如果对任意的v∈V(G),都有γ(Gv)<γ(G)成立,那么称G为γ-点临界图.本文主要给出Ananchuen和Plummer提出的一个猜想的证明,得到了如下的结果:若G是无K1,7的3-点临界图,且阶数为不小于18的偶数,则除几类特殊图外,G均有完美匹配.

Let γ（G） be the domination number of a graph G. A graph G is γ-vertex-critical if γ（G- v） 〈 γ（G） for every vertex v C V（G）. In this paper, we show that if G is a 3-vertex-critical graph of even order n ≥18 and K1,7-free, then G contains a perfect matching with some exceptions. Our result solves a conjecture proposed by Ananchuen and Plummer.