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 

出　　处：《Science China Mathematics》2010年第5期348-354,共7页中国科学：数学（英文版）

基　　金：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)

摘　　要：For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The 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(resp.domination edge critical) and γ(G) = k.Ananchuen 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 k-factor-critical.In 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.For a graph G =(V,E),a subset VS is a dominating set if every vertex in V is either in S or is adjacent to a vertex in S.The 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(resp.domination edge critical) and γ(G) = k.Ananchuen 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 k-factor-critical.In 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.

关 键 词：DOMINATION CRITICAL GRAPH FACTOR CRITICAL bicritical 

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