匹配可扩图的结构(英文)  

The Structure of Matching Extendable Graphs

作　　者：张东艳[1] 王世英[2] 李湘露[3] 

机构地区：[1]晋中师专数学系,山西榆次030600 [2]华中科技大学控制科学与工程系,武汉430074 [3]郑州大学数学系,郑州450052

出　　处：《数学研究》2000年第4期360-366,共7页Journal of Mathematical Study

摘　　要：设G是一个有限的简单连通图 .D(G)表示V(G)的一个子集 ,它的每一个点至少有一个最大匹配不覆盖它 .A(G)表示V(G) -D(G)的一个子集 ,它的每一个点至少和D(G)的一个点相邻 .最后设C(G)=V(G) -A(G) -D(G) .在这篇文章中 ,下面的被获得 .(1)设u∈V(G) .若n≥ 1和G是n-可扩的 ,则(a)C(G-u) =和A(G-u)∪ {u}是一个独立集 ,(b)G的每个完美匹配包含D(G-u)的每个分支的一个几乎完美匹配 ,并且它匹配A(G-u)∪ {u}的所有点与D(G-u)的不同分支的点 .(2 )若G是 2 -可扩的 ,则对于u∈V(G) ,A(G -u) ∪ {u}是G的一个最大障碍且G的最大障碍的个数是 2或者是｜V(G)｜ .(3)设X=Cay(Q ,S) ,则对于u∈Q ,(a)A(X-u) = =C(G-u)和X-u是一个因子临界图 ,或者 (b)C(X-u) =和X的两部是A(X-u) ∪ {u}和D(X -u)且 ｜A(X-u)∪ {u} ｜=｜D(X-u)｜ .(4 )设X=Cay(Q ,S) ,则对于u∈Q ,A(X-u)∪ {u}是X的一个最大障碍且X的最大障碍的个数是 2或者是｜Q｜ .Let G be a simple finite connected graph. Denote by D(G) the set of all points in Gwhich are not covered by at least one maximum matching of G. Let A(G) be the set of points in V(G)-D(G) adjacent to at least one point in D(G). Finally let C(G)=V(G)-A(G)-D(G). In this paper,we obtain the following:(1) Let u∈V(G). If n1 and G is n-extendable,then:(a) C(G-u)= and A(G-u)∪｛u｝is an independent set,(b) each perfect matching of G contains a near-perfect matching of each component of D(G-u)and matches all points of A(G-u)∪｛u｝with points in distinct components of D(G-u).(2) If G is 2-extendable,then for u∈V(G),A(G-u)∪｛u｝is a maximum barrier in G. Moreover,the number of the maximum barriers of G is 2 or ｜V(G)｜. (3) Let X=Cay(Q,S)and ｜Q｜is even. Then for u∈Q,(a) A(X-u)==C(X-u)and X-u is factor-critical;or (b) C(X-u)= and the bipartition of X is A(X-u)∪｛u｝and D(X-u) with ｜A(X-u)∪｛u｝｜=｜D(X-u)｜. (4) Let X=Cay(Q,S) and ｜Q｜is even. Then for u∈Q, A(X-u)∪｛u｝is a maximum barrier in X. Moreover,the number of the maximum barriers of Xis 2 or ｜Q｜.

关 键 词：n-可扩 障碍 CAYLEY图 匹配可扩图 结构 简单连通图 

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