A conjecture on k-factor-critical and 3-γ-critical graphs

作     者：WANG Tao1&YU QingLin2 1Institute of Applied Mathematics,College of Mathematics and Information Science,Henan University,Kaifeng 475001,China 2Department of Mathematics and Statistics,Thompson Rivers University,Kamloops,BC V2C5N3,Canada 

作者机构：Institute of Applied Mathematics College of Mathematics and Information Science Henan University Kaifeng China Department of Mathematics and Statistics Thompson Rivers University Kamloops Canada 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2010年第53卷第5期

页      面：348-354页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：supported by Major State Basic Research Development Program of China (973 Project) (Grant No.2006CB805904) Natural Sciences and Engineering Research Council of Canada (Grant No.122059-200) 

主　　题：domination critical graph factor critical bicritical 

摘      要：For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in *** domination number γ(G) of G is the minimum order of a dominating set in G.A graph G is said to be domination vertex critical,if γ(G-v) γ(G) for any vertex v in G.A graph G is domination edge critical,if γ(G ∪ e) γ(G) for any edge e ∈/E(G).We call a graph G k-γ-vertex-critical(resp.k-γ-edge-critical) if it is domination vertex critical(*** edge critical) and γ(G) = *** and Plummer posed the conjecture:Let G be a k-connected graph with the minimum degree at least k+1,where k 2 and k≡|V|(mod 2).If G is 3-γ-edge-critical and claw-free,then G is *** this paper we present a proof to this conjecture,and we also discuss the properties such as connectivity and bicriticality in 3-γ-vertex-critical claw-free graph.