一類笛卡爾積圖的連通性

葛國菊 馬永梅

（巢湖學院數(shù)學系，安徽 巢湖 238024）

一類笛卡爾積圖的連通性

葛國菊 馬永梅

（巢湖學院數(shù)學系，安徽 巢湖 238024）

本文主要運用約化的方法證明了對圖集F上的任意圖H，則有H×Cm,m≥2，是Z3-連通的。

笛卡爾積；群連通；直系點

1 引言

寫本文的主要動機是由兩個猜想而引起的

猜想 1（ Bondy[1]）：4-邊連通圖有 Z3-NZF.

猜想 2（ Jaeger[2]）：5-邊連通圖是 Z3-連通的.

Kochol在[3]中證明了猜想1等價于5-邊連通圖有Z3-NZF，因此猜想2包含猜想1.由于H×Cm，m≥2為 5-正則圖，且當 m≥5時，H×Cm為5-邊連通的5-正則圖，因此根據(jù)猜想2它應該是Z3-連通的.本文主要用約化的方法證明了對圖集F上的任意圖H，則H×Cm，m≥2是Z3-連通的.本文中的圖都是指無環(huán)的有限圖，用到的群都是Abel群，對一個有限Abel群A，G是A-連通的，記作G∈＜A＞.一個非平凡的2-正則的連通圖稱為一個圈，一個圈有k-條邊，稱為k-圈，記作Ck.由Ck添加一個新頂點x，和k條邊xvi（i=1，2，…，k），其中 V(Ck)={v1,v2,…,vk}，所得到的圖稱為k-輪圖，記作Wk.設G是一個圖，v∈V(G)，d(v)≥4，令 N(v)={v1，v2，…，vm}為 v 的鄰點集，令 X={vv1，vv2}，則圖 G[v，X]是由 G{vv1,vv2}添加一條新邊v1v2所得到的圖.若H是G的子圖，記作H?G.以上的基本概念在[4]中有介紹.

命題 1 （H.-J.Lai[5]）：對任意 Abel群 A，＜A＞是一族連通圖滿足：

（1）K1∈＜A＞；

（2）若 e∈E(G),且 G∈＜A＞，則 G/e∈＜A＞；

（3）若 H?G 且 H，G/H∈＜A＞，則 G∈＜A＞；

（4）若|A|≥n+1,則 Cn∈＜A＞；

（5）若 G[v,X]∈＜A＞，則 G∈＜A＞.

命題 2 （M.Devos[6]）：對?n≥1，則有 W2n∈＜Z3＞.

若H?G，H∈＜A＞，則稱H為G的A-可收縮子圖，也可稱H上所有的點在A上都可收縮到H 上某點vH；要判斷 G∈＜A＞，根據(jù)命題1（3）知，只要判斷G/H∈＜A＞；G/H是把H上所有的點收縮成一點vH，再把所有的環(huán)去掉得到的圖；由命題 1（4）知 C2∈＜Z3＞，其中 V(C2)={v1,v2}，則稱 C2可收縮到點v1或v2可收縮到點v1.基本思想方法在[7]中有介紹.

2 主要結論

定義1：圖G和H的笛卡爾積，記作G×H，點集為 V(G)×V(H)={(g，h)：g∈V(G)，h∈V(H)}，對任意點(g1，h1)，(g2，h2)∈V(G×H)，若((g1，h1)，(g2，h2))∈E(G×H)，則 g1=g2，(h1，h2)∈E(H)或(g1，g2)∈E（G），h1=h2. 為了敘述方便令 V （H）={h1，h2， …，hn}，V（G）={g1，g2，…， gm}，在 G×H 中，一個層 G×{hi}稱為第i個 G-層；一個層{gj}×H稱為第 j個H-層；

定義2：F是為一個圖集滿足下列條件：

（1）Cn×e∈F，對?n≥2；（2）對?H1，H2∈F，在H1，H2上的任一塊的外圈上添加一點，并把這兩點用一條邊連起來所得到的圖為H，則H∈F.

由定義2可知F是一個塊樹集，即F上任意圖H的每一個塊都是一個Cn×e，n≥2，且塊與塊之間用一條邊連起來.

定義3：設H是F中的一個塊樹，H的每一個塊都是一個Cn×e，n≥2，選定H上的一個塊作為根塊，則其他塊有且只有一個父塊；每個塊上與父塊相連的點稱為直系點，則每個塊（非根塊）只有一個直系點；若把塊樹的各個塊看成一點，則一個塊點到根塊點的距離稱為該塊的層數(shù)，H中各塊點的層數(shù)的最大值稱為該塊樹H的樹高，其中根塊所在的層為第0層.

由定義3可知，若塊（非根塊）是引理5中的H，則直系點為 5；若塊（非根塊）是引理4中的H，則直系點為7；若塊（非根塊）是引理3中的H，則直系點為9；若塊（非根塊）是引理 1中的H，則直系點為11；若塊（非根塊）是引理2中的H，則直系點為2n+1.

通過研究主要得出以下結論：

定理 1： 對?H∈F，G=Cm，m≥2，則 G×H∈＜Z3＞.

在證明定理之前我們先看幾個引理，而下列引理及推論中需要用到以下幾個圖，我們先描述一下：

圖 G1=C3∪{v1，v2}，其中 V(C3)={1，2，3}，且 v1，v2與點 1，2，3 都相鄰；

圖 G2=Cm∪{v1}，其中 V(Cm)={1，2，…，m}（m≥4），且 v1與點 3，…，m 都相鄰，同時 v1與點 2形成2-圈；

圖 G3=Cm∪{v1，v2}，其中 V(Cm)={1，2，…，m}(m≥4)，且 v1與點 1，2，…，m 都相鄰，v2與點 2，3，…，m 都相鄰；

圖 G4=Cm∪{v1，v2}，其中 V(Cm)={1，2，…，m}(m≥4)，且 v1與點 1，2，…，m 都相鄰，v2與點 1，2都形成2-圈；

圖 G5=Cm×e∪{v1}，其中 V(Cm)={1，2，…，m}(m ≥4)，V(e)={g1，g2}， 且 v1與 點 (g1，1)， (g1，2)，..，(g1，m)都相鄰，同時 v1與點(g2，1)，(g2，2)也相鄰；

圖 G6=Cm×e∪{v1，v2}，其中 V(Cm)={1，2，…，m}(m ≥4)，V(e)={g1，g2}， 且 v1與 點 (g1，1)， (g1，2)，..，(g1，m)都相鄰，v2與點(g2，1)，(g2，2)，..，(g2，m)都相鄰.

容易證明它們都是Z3-連通的.

引理1：設H1為C5×e再把外圈細分所得到的圖，G=Cm，m≥2，記 V(H1)={1，2，3，4，5，6，7，8，9，10，11，12，13，14，15}，其中內圈上點按逆時針方向分別為{1，2，3，4，5}，外圈上點為{6，7，8，9，10}，且 1 和 6 相鄰，外圈上細分點為{11，12，13，14，15}， 且 11 與 7，8 相鄰， 在 G×H1中，H1上點12，13，14，15 所對應的 G-層上點都分別與 v12，v13，v14，v15相鄰， 令 T=G×H1∪{v12，v13，v14，v15}，則T∈＜Z3＞.

證明：（i）當m=2時，命題顯然成立；

（ii）當 m=3 時，記 V（G）={g1，g2，g3}，令（g1，6）為 v1，去掉邊（（g1，1），（g1，5）），（（g1，5），（g1，10））和((g1，10)，(g1，14))，添 加邊 （（g1，1），（g1，14）），去掉邊（（g1，1）， （g1，2）），（（g1，2），（g1，7））和 （（g1，7），（g1，15）），添加邊（（g1，1），（g1，15）），去 掉 邊（（g1，14）， （g2，14）） 和 （（g2，14）， （g2，6））， 添 加 邊（（g1，14），（g2，6））， 去掉邊 （（g1，15），（g2，15））和（（g2，15），（g2，6）），添加邊（（g1，15），（g2，6）），則 v1與（g1，1），（g1，14），（g1，15），（g2，6）形成 W4，由命題2知W4∈＜Z3＞，于是把這個W4收縮成一點，仍記為 v1，這時 v1與點（g2，1），（g3，6）都形成 2-圈，同時 v1與（g3，1），（g3，14），（g3，15）都相鄰，因此把點（g2，1），（g3，6），（g3，1），（g3，14），（g3，15）依次收縮到 v1，則 v1與點 v14，v15都形成 2-圈，把點v14，v15都收縮到 v1，此時 v1與點（g2，14），（g2，15）都形成 2-圈，所以可把點（g2，14），（g2，15）收縮到v1。 則這時，一方面 v1與（g2，5），（g2，10），（g3，5），（g3，10）形成 W4，把（gi，5），（gi，10）（i=1，2，3）都收縮到 v1，則 v1與（gi，13）（i=1，2，3），v13形成 Z3-可收縮子圖G1，把它收縮成一點，仍記為v1，此時v1與（g2，4），（g2，9），（g3，4），（g3，9）形成 W4，把（gi，4），（gi，9）（i=1，2，3）都收縮到 v1，則 v1與（gi，12）（i=1，2，3），v12形成 Z3-可收縮子圖 G1， 把它收縮成一點，仍記為 v1，此時 v1與（g2，3），（g2，8），（g3，3），（g3，8）形成 W4，把（gi，3），（gi，8）（i=1，2，3）都收縮到 v1；另一方面 v1與（g2，2），（g2，7），（g3，2），（g3，7）形成 W4，把（gi，2），（gi，7）（i=1，2，3）都收縮到 v1，此時 v1與（gi，11）（i=1，2，3）都形成 2-圈，因此（gi，11）（i=1，2，3）都可收縮到 v1，由命題 1（5）知 T∈＜Z3＞.

（iii）當 m≥4 時，記 V（G）={g1，g2，…，gm}，令（g1，1）為 v1，去掉邊（（g1，6），（g1，14）），（（g1，14），（g1，10）） 和 （（g1，10），（g1，5））， 添加邊（（g1，6），（g1，5））；去掉邊（（g1，6），（g1，15）），（（g1，15），（g1，7））和（（g1，7），（g1，2）），添加邊（（g1，6），（g1，2））；去掉邊（（g1，5），（g2，5））和（（g2，5）， （g2，1），添加邊 （（g1，5），（g2，1））； 去掉邊 （（g1，2），（g2，2））和（（g2，2），（g2，1）），添加邊（（g1，2）， （g2，1））；則 v1與（g1，2），（g1，5），（g1，6），（g2，1）形成 W4，把這個W4收縮成一點，仍記為 v1，這時 v1與點(g2，6)形成2-圈，同時，v1與（g3，1），（g1，3），（g1，4），（gm，1），（gm，2），（gm，5），（gm，6） 都相鄰， 去掉邊（（gm，6），（gm，14）），（（gm，14），（gm，10）） 和 （（gm，10），（gm，5））， 添 加 邊 （（gm，6）， （gm，5））； 去 掉 邊 （（gm，6），（gm，15）），（（gm，15），（gm，7））和（（gm，7），（gm，2）），添加邊（（gm，6），（gm，2））；則 v1與（gm，1），（gm，2），（gm，5），（gm，6）形成 W4，把這個 W4收縮成一點，仍記為 v1，則 v1又與（gm-1，1），（gm-1，2），（gm-1，5），（gm-1，6）都相鄰，使用同樣的方法，去掉邊（（gj，6），（gj，14）），（（gj，14），（gj，10））和 （（gj，10），（gj，5）），添加邊（（gj，6），（gj，5））；去掉邊（（gj，6），（gj，15））， （（gj，15），（gj，7）） 和 （（gj，7），（gj，2））， 添 加邊 （（gj，6）， （gj，2）） 使 得 v1與 （gj，1）， （gj，2）， （gj，5），（gj，6），（j=m-1，m-2，...，4）形成 W4，把每形成這樣的W4都收縮成一點，仍記為v1，則v1又與（gj，3），（gj，4）（j=m， m-1， m-2，...，4） 都相鄰，同時 v1與（g3，2），（g3，5），（g3，6）也都相鄰，因此可把點（g2，6），（g3，1），（g3，2），（g3，5），（g3，6）依次收縮到 v1，則 v1與（g3，3），（g3，4）相鄰，這時去掉邊（v1，（g1，3）），（（g1，3），（g1，4）），添加邊（v1，（g1，4））；則v1與 （gi，4）（i=1，2， …，m） 形成 Z3-可收縮子圖G2，把它收縮成一點，仍記為 v1，再去掉邊（（g2，5）,（g2，10）），（（g2，10），（g2，13）） 和 （（g2，13），（g2，9）），添加邊（（g2，5），（g2，9））；這時 v1與（g2，5）形成 2-圈，把（g2，5）收縮到 v1，得 v1與（g2，9）形成2-圈，則 v1與（gi，9）（i=1，2，…，m）形成 Z3-可收縮子圖 G2，把它收縮成一點，仍記為 v1，則v1與（gi，13）（i=1，2， …，m），v13形成 Z3-可收縮子圖G3，把它收縮成一點，仍記為 v1，則 v1與（gi，10）（i=1，2，…，m）形成 Z3-可收縮子圖 G2，把它收縮成一點，仍記為 v1，則 v1與（gi，14）（i=1，2，…，m），v14形成Z3-可收縮子圖G4，把它收縮成一點，仍記為 v1，則 v1與（gi，12）（i=1，2，…，m），v12形成Z3-可收縮子圖G3，把它收縮成一點，仍記為v1，則 v1與（gi，3），（gi，8）（i=1，2，…，m）形成 Z3-可收縮子圖G5，把它收縮成一點，仍記為v1，這時v1與（g2，2）形成 2-圈，把（g2，2）收縮到 v1，則 v1，（gi，7），（gi，11）（i=1，2， …，m） 形成 Z3-可收縮子圖G5，把它收縮成一點，仍記為 v1，則 v1與（gi，15）（i=1，2，…，m），v15形成 Z3-可收縮子圖 G4，把它收縮成一點，仍記為 v1，由命題 1（5）知 T∈＜Z3＞.

推論1：引理1中的H1的外圈上有沒有點12，13，14，15或有更多這樣的點都不影響 T 的Z3-連通性；沒有點11或者點11是和點12一樣的點也不影響T的Z3-連通性.

證明：（i）當m=2時，命題顯然成立；

（ii）當 m=3 時，由引理 1（ii）的證明知有沒有點12，13或有更多這樣的點都不影響T的Z3-連通性，同時沒有點11也不影響T的Z3-連通性，因為在證明過程中它們都是單獨進行Z3-收縮的。 若沒有點 15，則在把 v1與（g1，1），（g1，7），（g1，14），（g2，6） 形成的 W4收縮成到 v1后， 則 v1與（g2，1），（g3，6）都形成 2-圈，同時 v1與（g3，1），（g3，14），（g3，7），（g1，11）都相鄰，因此（g2，1），（g3，6），（g3，1），（g3，14），（g3，7）依次收縮到 v1，此時 v1與點（g3，2）形成 2-圈，同時 v1與（g2，2），（g2，3）相鄰，則（g3，2），（g2，2），（g1，2）都可收縮到 v1，其它的與引理1（ii）類似.若沒有點14，與沒有點 15證明類似.若點11是和點12一樣的點，則在把（gi，11）（i=1，2，3）都收縮到 v1之后，則 v1與 v11形成2-圈，即v11可收縮到v1.若在 H1的邊（7,11）上添加一個點 16，則 v1與（gi，11），（gi，16）（i=1，2，…，m），v16形成 Z3-可收縮子圖 G6，把它收縮成一點，仍記為 v1，則 v1與（gi，7）（i=1，2，…，m）形成Z3-可收縮子圖 G2；若在邊（7，11）上添加兩個或更多的點，因為每添加兩個點就會形成Z3-可收縮子圖G6，則可把添加的這兩個點看成只有一個點，其結果不影響T的Z3-連通性，因此更多的點都可看成只有一個點，其結果不影響T的Z3-連通性.

（iii）當 m≥4 時，由引理 1（iii）的證明知，有沒有點12，13，14，15或有更多這樣的點都不影響 T的 Z3-連通性；若沒有點 11，在引理 1（iii）的證明中當（gi，3），（gi，8）（i=1，2，…，m）都收縮到 v1后，則 v1與（gi，7）（i=1，2，…，m）形成 Z3-可收縮子圖G2；若點11是和點12一樣的點，則在把（gi，11）（i=1，2，…，m） 都收縮到 v1之后，則 v1與 v11形成2-圈，即v11可收縮到v1.其它證明類似，因此也不影響T的Z3-連通性.

引理 2：設 H1為 Cn×e，n≥6再把外圈細分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，…，n，n+1，…，2n，2n+1，…，3n}，其中內圈上點按逆時針方向分別為{1，2，…，n}，外圈上點為{n+1，n+2，…，2n}，且1和n+1相鄰，外圈上細分點為{2n+1，2n+2，…，3n}，且 2n+1 與 n+2，n+3 相鄰，在 G×H1中，H1上點 2n+2，2n+3， …，3n所對應的 G-層上點都分別與 v2n+2，v2n+3，…，v3n相鄰，令 T=G×H1∪{v2n+2，v2n+3，…，v3n}，則 T∈＜Z3＞.

證明：這里的H1可看成是由引理1中的H1在邊（3，4）和（8，9）上都添加了 n-5 個點，并把對應的點之間連一條邊，同時在邊（8，9）上還添加了像點12這樣的點若干個而形成的圖。由引理1的證明知道，當（gi，n-1），（gi，2n-1）（i=1，2，…，m）都收縮到 v1后，每遇到（gi，j），（gi，n+j）（i=1，2，…，m）（j=n-2，n-3，…，4）在 G×H1中形成的圖與v1形成Z3-可收縮子圖G5，把它收縮成一點，仍記為v1；每遇到像12這樣的點在G×H1中形成的圖與v1及v12形成Z3-可收縮子圖G3，把它收縮成一點，仍記為v1，其它證明與引理1類似，因此T∈＜Z3＞.

推論2：引理2中的H1的外圈Cn上有沒有點2n+2，2n+3，…，3n或有更多這樣的點都不影響T的Z3-連通性；沒有點2n+1或者點2n+1是和點2n+2一樣的點也不影響T的Z3-連通性.

證明與推論1類似.

引理3：設H1為C4×e再把外圈細分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，3，4，5，6，7，8，9，10，11，12}， 其中內圈上點按逆時針方向分別為{1，2，3，4}，外圈上點為{5，6，7，8}，且 1 和 5 相鄰，外圈上細分點為{9，10，11，12}，且 9 與 6，7 相鄰， 在 G×H1中，H1上點 10，11，12 所對應的 G-層上點都分別與 v10，v11，v12相鄰， 令 T=G×H1∪{v10，v11，v12}，則 T∈＜Z3＞.

證明：這里的H1可看成是引理1中的H1上沒有點3，8，12，證明與引理1類似.

推論3：引理3中的H1的外圈C4上有沒有點10，11，12或有更多這樣的點都不影響T的Z3-連通性；沒有點9或者點9是和點10一樣的點也不影響T的Z3-連通性.

證明與推論1類似.

引理4：設H1為C3×e再把外圈細分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，3，4，5，6，7，8，9}，其中內圈上點按逆時針方向分別為{1，2，3}，外圈上點為{4，5，6}，且 1和 4相鄰，外圈上細分點為{7，8，9}，且 7 與 5，6 相鄰，在 G×H1中，H1上點8，9所對應的G-層上點都分別與v8，v9相鄰，令 T=G×H1∪{v8，v9}，則 T∈＜Z3＞.

證明：（i）當 m=2時，命題顯然成立；

（ii）當 m=3 時，證明與引理 1（ii）類似.

（iii）當 m≥4 時，記 V（G）={g1，g2， …，gm}，令(g1，1)為 v1，去掉邊（（g1，4），（g1，8）），（（g1，8），（g1，6））和（（g1，6），（g1，3）），添加邊（（g1，4），（g1，3））；去掉邊（（g1，4），（g2，4））和（（g2，4），（g2，1）），添加邊 （（g1，4），（g2，1））； 去掉邊 （（g1，2），（g2，2））和（（g2，2），（g2，1）），添 加邊（（g1，2），（g2，1））；則 v1與（g1，2），（g1，3），（g1，4），（g2，1） 形成 W4，把這個W4收縮成一點，仍記為 v1，這時 v1與點（g2，3）形成 2-圈， 同時 v1與 （g3，1），（gm，1），（gm，2），（gm，3），（gm，4）都相鄰，再使用與引理 1（iii）中同樣的方法，去掉邊（（gj，4），（gj，8）），（（gj，8），（gj，6））和（（gj，6），（gj，3）），添加邊（（gj，4），（gj，3））；使得 v1與 （gj，1）， （gj，2）， （gj，3）， （gj，4） （j=m，m-1，m-2，...，4）形成 W4，把每形成這樣的 W4都收縮成一點，仍記為 v1，則 v1與點（g3，1）形成 2-圈，同時 v1與（g3，2），（g3，3），（g3，4）都相鄰，因此點（g3，1），（g3，2），（g3，4），（g2，2），（g2，3）依次都可收縮到 v1，則 v1與（gi，5），（gi，9）（i=1，2，…，m）都相鄰，這時v1與（gi，5），（gi，9）（i=1，2，…，m）形成 Z3-可收縮子圖 G5，把它收縮成一點，仍記為 v1，則 v9與 v1形成 2-圈，把 v9收縮到 v1，則 v1與（g2，4）形成 2-圈，把（g2，4）收縮到 v1，則 v1與（gi，6），（gi，7）（i=1，2，…，m）形成 Z3-可收縮子圖 G5，把它收縮成一點，仍記為 v1，則 v1與（gi，8）（i=1，2，…，m）及 v8形成 Z3-可收縮子圖 G4，由命題 1（5）知 T∈＜Z3＞.

推論4：引理4中的H1的外圈C3上有沒有點8，9或有更多這樣的點都不影響T的Z3-連通性；沒有點7或者點7是和點8一樣的點也不影響T的Z3-連通性.

證明與推論1類似.

引理5：設H1為C2×e再把外圈細分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，3，4，5，6}，其中內圈上點按逆時針方向分別為{1，2}，外圈上點為{3，4}，且 1 和 3 相鄰，外圈上細分點為{5，6}，且5與3，4相鄰， 在 G×H1中，H1上點 6所對應的G-層上點都分別與v6相鄰，令T=G×H1∪{v6}，則 T∈＜Z3＞.

證明：（i）當m=2時，命題顯然成立；

（ii）當 m≥3 時，記 V(G)={g1，g2，…，gm}，由已知（gi，1），（gi，2）（i=1，2，…，m）都形成 2-圈，則可把（gi，1），（gi，2）（i=1，2，…，m）收縮成一點，記為v1，則 v1與（gi，3），（gi，4）（i=1，2，…，m）都相鄰，去掉邊（v1，（g1，3））和（（g1，3），（g2，3）），添加邊（v1，（g2，3）） ，則這時 v1與點（g2，3）形成 2-圈，從而（gj，3）（j=2，3，…，m）依次都可收縮到 v1，此時則v1與（gi，4），（gi，5）（i=1，2，…，m）形成 Z3-可收縮子圖 G5，把它收縮成一點，仍記為 v1，則 v1與（gi，6）（i=1，2，…，m）及 v6形成 Z3-可收縮子圖 G3，這時 v1與點（g1，3）形成 2-圈，則（g1，3）也可收縮v1，由命題 1（5）知 T∈＜Z3＞.

推論5：引理5中的H1的外圈C2上有沒有點6或有更多這樣的點都不影響T的Z3-連通性；沒有點5或者點5是和點6一樣的點也不影響T的Z3-連通性.

證明與推論1類似.

證明定理1：由于H是一個塊樹，任意選定一個塊作為根塊，不妨H設有n層，從第n-1層開始，由推論 1，2，3，4，5 可知，第 n-1 層的葉塊與G的笛卡爾積圖都是Z3-可收縮的，則把它們都收縮成一點 （若葉塊與其父塊上某點i相連），記為vi，則父塊中i點在G×H中形成的圈Cm上的點都與vi相鄰，形成Wm，其中vi為中心；再由引理 1，2，3，4，5 及推論 1，2，3，4，5 知，第 n-2 層的各個塊與G的笛卡爾積圖也都是Z3-可收縮的，再把它們都收縮成一點（若與其父塊上某點j相連），記為vj，以此類推，第n-3層、第n-4層、、、第1層、第0層的各個塊與G的笛卡爾積圖也都是Z3-可收縮的，到最后可把G×H收縮成一點，因此 G×H∈＜Z3＞.

[1]Bondy,J.A.,Murth,U.S.R.graph Theory with Applications New york:American Elsevier,1976.

[2]F.Jaeger,N.Linial.C.Payan,M.Tarsi,Group connectivity of graphs-a nonhomogeneons analogue of nowhere-zero flow properties.J.Comb.Theory,Ser.B56,165-182(1992).

[3]Kochol,M.An equivalent version of the 3-flow conjecture.J.Combin.Theory Ser.B83,258-261(2001).

[4]Zhang,C.Q.Integer flows and cycle covers of graphs.New york:Marcel Dekker.1997.

[5]H.-J.Lai,group connectivity of 3-edge-connected chordal graphs.Graphs and Combinatorics,16(2000).165-176.

[6]M.Devos,R.Xu,and G.Yu,Nowthere-zero Z3-flows through Z3-connectivity，Discrete Math,306(2006)26-30.

[7]H.-J.Lai,Nowthere-zero 3-flows in locally connected graphs.J.Graph Theory,42(2003).N0.3,211-219.

ON GROUP CONNECTIVITY OF THE CARTESIAN PRODUCT

GE Guo-ju MA Yong-mei
(Department of Mathematics,Chaohu College,Chaohu Anhui 238024)

In this paper,by reduction methods proved that for any graph H on the graph collection F,then H×Cm,m≥2 is Z3-connectivity.

Cartesian product;group-connectivity;direct-point

0157.5

A

1672-2868（2011）03-0017-05

2011-02-28

葛國菊（1981-），女，安徽含山人。巢湖學院數(shù)學系助教，研究方向：圖論

責任編輯：陳 侃