葛国菊 王 涛

(1.巢湖学院数学系，安徽巢湖 238024;2.华北科技学院基础部，北京东燕郊 101601)

一类Snark与k-圈的卡式积图的连通性①

葛国菊1②王 涛2

(1.巢湖学院数学系，安徽巢湖 238024;2.华北科技学院基础部，北京东燕郊 101601)

本文主要运用约化的方法证明了Flower snark Jk与Cm的卡式积图Jk×Cm是Z3-连通的。

卡式积;群连通;收缩

1 引言

写本文的主要动机是由两个猜想而引起的。

猜想 1(Bondy［1］):4-边连通图有 Z3-NZF。

猜想2(Jaeger［2］):5-边连通图是Z3-连通的。

Kochol在［3］中证明了猜想1等价于5-边连通图有Z3-NZF，因此猜想2包含猜想1。由于Jk×Cm，m≥2为5-正则图，且当m≥5时，Jk×Cm为5-边连通的5-正则图，因此根据猜想2它应该是Z3-连通的。从而，旁证了以上两个猜想。本文主要用约化的方法证明了Jk×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。……