一类笛卡尔积图的连通性

葛国菊 马永梅

（巢湖学院数学系，安徽 巢湖 238024）

一类笛卡尔积图的连通性

葛国菊 马永梅

（巢湖学院数学系，安徽 巢湖 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-正则图，因此根据猜想2它应该是Z3-连通的.本文主要用约化的方法证明了对图集F上的任意图H，则H×Cm，m≥2是Z3-连通的.本文中的图都是指无环的有限图，用到的群都是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＞，根据命题1（3）知，只要判断G/H∈＜A＞；G/H是把H上所有的点收缩成一点vH，再把所有的环去掉得到的图；由命题 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上的一个块作为根块，则其他块有且只有一个父块；每个块上与父块相连的点称为直系点，则每个块（非根块）只有一个直系点；若把块树的各个块看成一点，则一个块点到根块点的距离称为该块的层数，H中各块点的层数的最大值称为该块树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-），女，安徽含山人。巢湖学院数学系助教，研究方向：图论

责任编辑：陈 侃