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

A conjecture on 3-vertex-critical graphs

作　　者：刘慧清[1] 陆玫[2] 章舜哲[1] 

机构地区：[1]湖北大学数学与计算机科学学院,武汉430062 [2]清华大学数学科学系,北京100084

出　　处：《中国科学：数学》2013年第5期519-527,共9页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:10990011和11171097)资助项目

摘　　要：设γ(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.

关 键 词：点控制数 3-点临界图 完美匹配 

分 类 号：O157.5[理学—数学]