一類笛卡爾積圖的連通性

葛國(guó)菊 馬永梅

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

一類笛卡爾積圖的連通性

葛國(guó)菊 馬永梅

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

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

笛卡爾積；群連通；直系點(diǎn)

1 引言

寫本文的主要?jiǎng)訖C(jī)是由兩個(gè)猜想而引起的

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

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

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

命題 1 （H.-J.Lai[5]）：對(duì)任意 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]）：對(duì)?n≥1，則有 W2n∈＜Z3＞.

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

2 主要結(jié)論

定義1：圖G和H的笛卡爾積，記作G×H，點(diǎn)集為 V(G)×V(H)={(g，h)：g∈V(G)，h∈V(H)}，對(duì)任意點(diǎn)(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è)層 G×{hi}稱為第i個(gè) G-層；一個(gè)層{gj}×H稱為第 j個(gè)H-層；

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

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

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

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

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

通過(guò)研究主要得出以下結(jié)論：

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

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

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

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

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

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

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

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

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

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

證明：（i）當(dāng)m=2時(shí)，命題顯然成立；

（ii）當(dāng) m=3 時(shí)，記 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＞，于是把這個(gè)W4收縮成一點(diǎn)，仍記為 v1，這時(shí) v1與點(diǎn)（g2，1），（g3，6）都形成 2-圈，同時(shí) v1與（g3，1），（g3，14），（g3，15）都相鄰，因此把點(diǎn)（g2，1），（g3，6），（g3，1），（g3，14），（g3，15）依次收縮到 v1，則 v1與點(diǎn) v14，v15都形成 2-圈，把點(diǎn)v14，v15都收縮到 v1，此時(shí) v1與點(diǎn)（g2，14），（g2，15）都形成 2-圈，所以可把點(diǎn)（g2，14），（g2，15）收縮到v1。 則這時(shí)，一方面 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，把它收縮成一點(diǎn)，仍記為v1，此時(shí)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， 把它收縮成一點(diǎn)，仍記為 v1，此時(shí) 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，此時(shí) v1與（gi，11）（i=1，2，3）都形成 2-圈，因此（gi，11）（i=1，2，3）都可收縮到 v1，由命題 1（5）知 T∈＜Z3＞.

（iii）當(dāng) m≥4 時(shí)，記 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，把這個(gè)W4收縮成一點(diǎn)，仍記為 v1，這時(shí) v1與點(diǎn)(g2，6)形成2-圈，同時(shí)，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，把這個(gè) W4收縮成一點(diǎn)，仍記為 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都收縮成一點(diǎn)，仍記為v1，則v1又與（gj，3），（gj，4）（j=m， m-1， m-2，...，4） 都相鄰，同時(shí) v1與（g3，2），（g3，5），（g3，6）也都相鄰，因此可把點(diǎn)（g2，6），（g3，1），（g3，2），（g3，5），（g3，6）依次收縮到 v1，則 v1與（g3，3），（g3，4）相鄰，這時(shí)去掉邊（v1，（g1，3）），（（g1，3），（g1，4）），添加邊（v1，（g1，4））；則v1與 （gi，4）（i=1，2， …，m） 形成 Z3-可收縮子圖G2，把它收縮成一點(diǎn)，仍記為 v1，再去掉邊（（g2，5）,（g2，10）），（（g2，10），（g2，13）） 和 （（g2，13），（g2，9）），添加邊（（g2，5），（g2，9））；這時(shí) v1與（g2，5）形成 2-圈，把（g2，5）收縮到 v1，得 v1與（g2，9）形成2-圈，則 v1與（gi，9）（i=1，2，…，m）形成 Z3-可收縮子圖 G2，把它收縮成一點(diǎn)，仍記為 v1，則v1與（gi，13）（i=1，2， …，m），v13形成 Z3-可收縮子圖G3，把它收縮成一點(diǎn)，仍記為 v1，則 v1與（gi，10）（i=1，2，…，m）形成 Z3-可收縮子圖 G2，把它收縮成一點(diǎn)，仍記為 v1，則 v1與（gi，14）（i=1，2，…，m），v14形成Z3-可收縮子圖G4，把它收縮成一點(diǎn)，仍記為 v1，則 v1與（gi，12）（i=1，2，…，m），v12形成Z3-可收縮子圖G3，把它收縮成一點(diǎn)，仍記為v1，則 v1與（gi，3），（gi，8）（i=1，2，…，m）形成 Z3-可收縮子圖G5，把它收縮成一點(diǎn)，仍記為v1，這時(shí)v1與（g2，2）形成 2-圈，把（g2，2）收縮到 v1，則 v1，（gi，7），（gi，11）（i=1，2， …，m） 形成 Z3-可收縮子圖G5，把它收縮成一點(diǎn)，仍記為 v1，則 v1與（gi，15）（i=1，2，…，m），v15形成 Z3-可收縮子圖 G4，把它收縮成一點(diǎn)，仍記為 v1，由命題 1（5）知 T∈＜Z3＞.

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

證明：（i）當(dāng)m=2時(shí)，命題顯然成立；

（ii）當(dāng) m=3 時(shí)，由引理 1（ii）的證明知有沒(méi)有點(diǎn)12，13或有更多這樣的點(diǎn)都不影響T的Z3-連通性，同時(shí)沒(méi)有點(diǎn)11也不影響T的Z3-連通性，因?yàn)樵谧C明過(guò)程中它們都是單獨(dú)進(jìn)行Z3-收縮的。 若沒(méi)有點(diǎn) 15，則在把 v1與（g1，1），（g1，7），（g1，14），（g2，6） 形成的 W4收縮成到 v1后， 則 v1與（g2，1），（g3，6）都形成 2-圈，同時(shí) v1與（g3，1），（g3，14），（g3，7），（g1，11）都相鄰，因此（g2，1），（g3，6），（g3，1），（g3，14），（g3，7）依次收縮到 v1，此時(shí) v1與點(diǎn)（g3，2）形成 2-圈，同時(shí) v1與（g2，2），（g2，3）相鄰，則（g3，2），（g2，2），（g1，2）都可收縮到 v1，其它的與引理1（ii）類似.若沒(méi)有點(diǎn)14，與沒(méi)有點(diǎn) 15證明類似.若點(diǎn)11是和點(diǎn)12一樣的點(diǎn)，則在把（gi，11）（i=1，2，3）都收縮到 v1之后，則 v1與 v11形成2-圈，即v11可收縮到v1.若在 H1的邊（7,11）上添加一個(gè)點(diǎn) 16，則 v1與（gi，11），（gi，16）（i=1，2，…，m），v16形成 Z3-可收縮子圖 G6，把它收縮成一點(diǎn)，仍記為 v1，則 v1與（gi，7）（i=1，2，…，m）形成Z3-可收縮子圖 G2；若在邊（7，11）上添加兩個(gè)或更多的點(diǎn)，因?yàn)槊刻砑觾蓚€(gè)點(diǎn)就會(huì)形成Z3-可收縮子圖G6，則可把添加的這兩個(gè)點(diǎn)看成只有一個(gè)點(diǎn)，其結(jié)果不影響T的Z3-連通性，因此更多的點(diǎn)都可看成只有一個(gè)點(diǎn)，其結(jié)果不影響T的Z3-連通性.

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

引理 2：設(shè) H1為 Cn×e，n≥6再把外圈細(xì)分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，…，n，n+1，…，2n，2n+1，…，3n}，其中內(nèi)圈上點(diǎn)按逆時(shí)針?lè)较蚍謩e為{1，2，…，n}，外圈上點(diǎn)為{n+1，n+2，…，2n}，且1和n+1相鄰，外圈上細(xì)分點(diǎn)為{2n+1，2n+2，…，3n}，且 2n+1 與 n+2，n+3 相鄰，在 G×H1中，H1上點(diǎn) 2n+2，2n+3， …，3n所對(duì)應(yīng)的 G-層上點(diǎn)都分別與 v2n+2，v2n+3，…，v3n相鄰，令 T=G×H1∪{v2n+2，v2n+3，…，v3n}，則 T∈＜Z3＞.

證明：這里的H1可看成是由引理1中的H1在邊（3，4）和（8，9）上都添加了 n-5 個(gè)點(diǎn)，并把對(duì)應(yīng)的點(diǎn)之間連一條邊，同時(shí)在邊（8，9）上還添加了像點(diǎn)12這樣的點(diǎn)若干個(gè)而形成的圖。由引理1的證明知道，當(dāng)（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，把它收縮成一點(diǎn)，仍記為v1；每遇到像12這樣的點(diǎn)在G×H1中形成的圖與v1及v12形成Z3-可收縮子圖G3，把它收縮成一點(diǎn)，仍記為v1，其它證明與引理1類似，因此T∈＜Z3＞.

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

證明與推論1類似.

引理3：設(shè)H1為C4×e再把外圈細(xì)分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，3，4，5，6，7，8，9，10，11，12}， 其中內(nèi)圈上點(diǎn)按逆時(shí)針?lè)较蚍謩e為{1，2，3，4}，外圈上點(diǎn)為{5，6，7，8}，且 1 和 5 相鄰，外圈上細(xì)分點(diǎn)為{9，10，11，12}，且 9 與 6，7 相鄰， 在 G×H1中，H1上點(diǎn) 10，11，12 所對(duì)應(yīng)的 G-層上點(diǎn)都分別與 v10，v11，v12相鄰， 令 T=G×H1∪{v10，v11，v12}，則 T∈＜Z3＞.

證明：這里的H1可看成是引理1中的H1上沒(méi)有點(diǎn)3，8，12，證明與引理1類似.

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

證明與推論1類似.

引理4：設(shè)H1為C3×e再把外圈細(xì)分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，3，4，5，6，7，8，9}，其中內(nèi)圈上點(diǎn)按逆時(shí)針?lè)较蚍謩e為{1，2，3}，外圈上點(diǎn)為{4，5，6}，且 1和 4相鄰，外圈上細(xì)分點(diǎn)為{7，8，9}，且 7 與 5，6 相鄰，在 G×H1中，H1上點(diǎn)8，9所對(duì)應(yīng)的G-層上點(diǎn)都分別與v8，v9相鄰，令 T=G×H1∪{v8，v9}，則 T∈＜Z3＞.

證明：（i）當(dāng) m=2時(shí)，命題顯然成立；

（ii）當(dāng) m=3 時(shí)，證明與引理 1（ii）類似.

（iii）當(dāng) m≥4 時(shí)，記 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，把這個(gè)W4收縮成一點(diǎn)，仍記為 v1，這時(shí) v1與點(diǎn)（g2，3）形成 2-圈， 同時(shí) 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都收縮成一點(diǎn)，仍記為 v1，則 v1與點(diǎn)（g3，1）形成 2-圈，同時(shí) v1與（g3，2），（g3，3），（g3，4）都相鄰，因此點(diǎn)（g3，1），（g3，2），（g3，4），（g2，2），（g2，3）依次都可收縮到 v1，則 v1與（gi，5），（gi，9）（i=1，2，…，m）都相鄰，這時(shí)v1與（gi，5），（gi，9）（i=1，2，…，m）形成 Z3-可收縮子圖 G5，把它收縮成一點(diǎn)，仍記為 v1，則 v9與 v1形成 2-圈，把 v9收縮到 v1，則 v1與（g2，4）形成 2-圈，把（g2，4）收縮到 v1，則 v1與（gi，6），（gi，7）（i=1，2，…，m）形成 Z3-可收縮子圖 G5，把它收縮成一點(diǎn)，仍記為 v1，則 v1與（gi，8）（i=1，2，…，m）及 v8形成 Z3-可收縮子圖 G4，由命題 1（5）知 T∈＜Z3＞.

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

證明與推論1類似.

引理5：設(shè)H1為C2×e再把外圈細(xì)分所得到的圖，G=Cm，m≥2，記 V（H1）={1，2，3，4，5，6}，其中內(nèi)圈上點(diǎn)按逆時(shí)針?lè)较蚍謩e為{1，2}，外圈上點(diǎn)為{3，4}，且 1 和 3 相鄰，外圈上細(xì)分點(diǎn)為{5，6}，且5與3，4相鄰， 在 G×H1中，H1上點(diǎn) 6所對(duì)應(yīng)的G-層上點(diǎn)都分別與v6相鄰，令T=G×H1∪{v6}，則 T∈＜Z3＞.

證明：（i）當(dāng)m=2時(shí)，命題顯然成立；

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

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

證明與推論1類似.

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

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

責(zé)任編輯：陳 侃