(2n+1)-可收缩图和2n-对可收缩图  

On(2n+1)-Contractible Graphs and 2n-Pairs Contractible Graphs

作　　者：林泓[1] 郭晓峰[2] 

机构地区：[1]集美大学理学院,厦门361021 [2]厦门大学数学科学学院,厦门361005

出　　处：《数学学报（中文版）》2009年第2期343-352,共10页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金(10331020);福建省教育厅基金(JA07143);集美大学自然科学基金资助项目

摘　　要：令G是一个简单连通图.设S■V(G)且|S|=2n+1,将S收缩为一个顶点后所得到的图记α_((2n+1))(G,S).若G有完美匹配,且对于V(G)的任意一个有2n+1个顶点的子集S,图α_((2n+1))(G,S)有完美匹配,则称G是一个(2n+1)-可收缩图.设S_1,S_2,…,S_(2n)是V(G)的两两不相交的子集且|S_1|=|S_2|=…=|S_(2n)|=2,将S_i (i=1,2,…,2n)分别收缩为一点所得到的图记β_(2n)(G,S_1,S_2,…,S_(2n)).若G有完美匹配,且对于V(G)的任意2n个两两不相交的子集S_1,S_2,…,S_(2n),这里|S_1|=|S_2|=…=|S_(2n)|=2,图β_(2n)(G,S_1,S_2,…,S_(2n))有完美匹配,则称G是一个2n-对可收缩图.本文得到了(2n+1)-可收缩图和2n-对可收缩图的充要条件,并讨论了2n-临界图,(2n+1)-可收缩图,2n-对可收缩图及n-可扩图间的关系.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 S1, S2,...,S2n of V（G） with ｜S1｜ = ｜S2｜=…= ｜S2n｜ = 2, let β2n（G, S1, S2,..., S2n） denote the graph obtained from G by contracting each Si （i = 1, 2,..., 2n） to a single vertex respectively. If G has a perfect matching and for any pairwise disjoint subsets S1,S2,..., S2n of V（G） with ｜S1｜ = ｜S2｜… ｜S2n｜ = 2, the graph β2n（G, S1,S2,... ,S2n） has a perfect matching, then G is called a 2npairs 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.

关 键 词：(2n+1)-可收缩图 2n-对可收缩图 N-可扩图 k-临界图 

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