Hong LIN School of Sciences,Jimei University,Xiamen 361021,P.R.China Xiao Feng GUO School of Mathematical Sciences,Xiamen University,Xiamen 361005,P.R.China
Let G be a simple connected graph.For a subset S of V(G) with |S|=2n+1, letα_((2n+1))(G,S) denote the graph obtained from G by contracting S to a single vertex. If G has a perfect matching and,for any subset S of V(G) with |S|=2n+1,the graphα_((2n+1))(G,S) has a perfect matching,then G is called a(2n+1)-contractible graph. For pairwise disjoint subsets S_1,S_2,...,S_(2n) of V(G) with |S_1|=|S_2|=…=|S_2|=2, letβ_(2n)(G,S_1,S_2,...,S_(2n)) denote the graph obtained from G by contracting each S_i (i=1,2,...,2n) to a single vertex respectively.If G has a perfect matching and for any palrwise disjoint subsets S_1,S_2,...,S_(2n) of V(G) with |S_1|=|S_2|=…=|S_(2n)|= 2,the graphβ_(2n)(G,S_1,S_2,...,S_(2n)) has a perfect matching,then G is called a 2n-pairs contractible graph.In the present paper,some simple necessary and sufficient conditions for a graph to be a(2n+1)-contractible graph(resp.a 2n-pairs contractible) graph are established.The relations between 2n-critical graphs,(2n+1)-contractible graphs,2n-pairs contractible graphs,and n-extendable graphs are investigated.
