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

葛国菊 王 涛

(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。为了叙述方便令 V(H)={h1，h2，…，hn}，V(G)={g1，g2，…，gm}，在 G × H 中，一个层 G × {hi}称为第i个G-层;一个层{gj}×H称为第j个H-层;

定义2:对奇整数 k，k≥3，Flower snark Jk结构如下:

V(Jk)={v1，v2，...，vk}∪{1，2，...，k，k+1，k+2，...，2k，2k+1，2k+2，...，3k}，图 Jk有4k 个顶点，是由一个 k 长圈1，2，...，k，1 和一个2k 长圈 k+1，k+2，...，2k，2k+1，2k+2，...，3k，k+1 组成，另外添加顶点 vi(i=1，2，...，k)与i，k+i和 2k+i都相邻。例如 J5，J7的图如下:

定理1:G=Cm，m≥2的整数，则 Jk×G∈＜Z3＞。

为了证明这个定理，我们先看一个引理。

引理1设 G1，G2，G3满足下列条件，则 G1，G2，G3都是 Z3- 连通的。

(1)G1是由 K1，3× C3和点 v 组成，设 V(K1，3)={v1，1，2，3}，V(C3)={g1，g2，g3}，且在 G1中 v与点(g1，1)，(g1，3)，(g2，2)，(g3，1)，(g3，2)，(g3，3)相邻。

(2)G2是由 K1，3× C2l+1和点 v 组成，设 V(K1，3)={v1，1，2，3}，V(C2l+1)={g1，g2，...，g2l+1}，且在 G2中 v 与点(gi，1)，(gi，3)，(gj，2)，i=1，3，...，2l+1，j=2，4，...，2l，2l+1 都相邻。

(3)G3是由 K1，3× C2l和点 v 组成，设 V(K1，3)={v1，1，2，3}，V(C2l)={g1，g2，...，g2l}，且在 G3中 v 与点(gi，1)，(gi，3)，(gj，2)，i=1，3，...，2l-1，

2l，j=2，4，...，2l-2，2l-1 都相邻。

证明:(1)去掉边(v，(g1，1))，((g1，1)，(g1，v1))，((g1，v1)，(g1，3))，添加边(v，(g1，3))，则v与(g1，3)形成 2-圈，又因为 v与点(g3，3)相邻，所以点(g1，3)，(g2，3)，(g3，3)依次都可收缩到 v，则 v 与点(g2，v1)，(g3，v1)都相邻，又因为 v与点(g2，2)，(g3，2)相邻，所以 v 与点(g2，v1)，(g3，v1)，(g2，2)，(g3，2)形成 W4，则(g1，v1)，(g2，v1)，(g3，v1)，(g1，2)，(g2，2)，(g3，2)都可收缩到v，这时v 与(g3，1)形成2-圈，v 与点(g2，1)相邻，因此(g1，1)，(g2，1)，(g3，1)依次也都可收缩到 v，根据命题1(5)知，G1∈ ＜Z3＞。

(2)去掉边(v，(g1，1))，((g1，1)，(g1，v1))，((g1，v1)，(g1，3))，添加边(v，(g1，3))，则v与(g1，3)形成2-圈，又因为 v与点(g2l+1，3)相邻，所点(g1，3)，(g2l+1，3)都可收缩到 v，则 v 与点(g2，3)，(g2l，3)，(g2l+1，v1)都相邻，再去掉边(v，(g2l+1，2))，((g2l+1，2)，(g2l+1，v1))，添加边(v，(g2l+1，v1))，则点(g2l+1，v1)，(g2l+1，1)依次可收缩到 v，则 v 与点(g2l，v1)，(g2l，1)都相邻，再去掉(v，(g2l-1，3))，((g2l-1，3)，g2l-1，v1)，添加边(v，(g2l-1，v1))，则 v 与点(g2l，v1)，(g2l-1，v1)，(g2l，1)，(g2l-1，1)形成 W4，把它收缩到 v，则点(g2l，2)，(g2l-1，2)，(g2l-2，2)，(g2l-2，v1)，(g2l-2，1)，

(g2l-3，1)，(g2l-3，v1)，(g2l-3，2)，(g2l-4，2)，...，(g2，2)，(g2，v1)，(g2，1)，(g1，1)，(g1，v1)，(g1，2)依次都可收缩到 v，此时 v 与(g2，3)，(g3，3)，(g5，3)，...，(g2l-3，3)，(g2l-2，3)，(g2l，3)都形成 2- 圈，因此(g2，3)，(g3，3)，(g4，3)，...，(g2l-2，3)，(g2l，3)都可收缩到 v，这时 v 与(g2l-1，3)也形成2-圈，根据命题1(5)知，G2∈＜Z3＞。

(3)去掉边(v，(g1，1))，((g1，1)，(g1，v1))，((g1，v1)，(g1，3))，添加边(v，(g1，3))，则v与(g1，3)形成 2- 圈，又因为 v 与点(g2l-1，3)，(g2l，3)相邻，所以点(g1，3)，(g2l，3)，(g2l-1，3)都可收缩到 v，则 v 与点(g2l，v1)，(g2l-1，v1)都相邻，又因为 v 与点(g2l，1)，(g2l，1)相邻，所以 v 与点(g2l，v1)，(g2l-1，v1)，(g2l，1)，(g2l-1，1)形成W4，把它收缩到 v，则点 (g2l-1，2)，(g2l，2)，(g2l-2，2)，(g2l-2，v1)，(g2l-2，1)，(g2l-2，3)，...，(g2，2)，(g2，v1)，(g2，1)，(g2，3)，(g1，v1)，(g1，1)，(g1，2)都依次可收缩到 v，根据命题1(5)知，G3∈＜Z3＞。

证明定理1(i)当m=2时，命题显然成立;

(ii)当 m=3时，记 V(G)={g1，g2，g3}，利用命题 1(5)，去掉边((g1，1)，(g1，k))，((g1，k)，(g1，vk))，((g1，vk)，(g1，3k))，((g1，3k})，(g1，k+1))，添加边((g1，1)，(g1，k+1))去掉边((g1，k+1)，(g1，k+2))，((g1，k+2)，(g1，k+3))，...，((g1，2k-1)，(g1，2k))，((g1，2k)，(g1，2k+1))，添加边((g1，k+1)，(g1，2k+1));去掉边((g1，1)，(g2，1))，((g2，1)，(g2，v1))，添加边((g1，1)，(g2，v1));去掉边((g1，2k+1)，(g2，2k+1))，((g2，2k+1)，(g2，v1))，添加边((g1，2k+1)，(g2，v1));使得(g1，v1)与(g1，1)，(g1，k+1)，(g1，2k+1)，(g2，v1)形成 W4，其中(g1，v1)是中心，把这个 W4收缩成一点，记为 v，这时 v与点(g2，k+1)，(g3，v1)都形成 2- 圈，v 与点(g1，2)，(g1，2k+2)相邻，同时 v 与(g3，1)，(g3，k+1)，(g3，2k+1)都相邻，因此把点(g2，k+1)，(g3，v1)，(g3，1)，(g3，k+1)，(g3，2k+1)依次收缩到 v，此时 v 点(g2，1)，(g2，k+2)，(g2，2k+1)，(g2，3k)都相邻，同时 v 与(g3，2)，(g3，k+2)，(g3，2k+2)，(g3，k)，(g3，2k)，(g3，3k)也都相邻，此时 v 与(gi，2)，(gi，k+2)，(gi，2k+2)，(gi，v2)，i=1，2，3 形成 Z3- 可收缩子图 G1(引理1中的G1)，把它收缩成一点，仍记为v，这时 v 与点(g2，1)，(g2，2k+1)都形成 2- 圈，则点(g2，1)，(g2，2k+1)都可收缩到 v，则类似的 v 与(gi，j)，(gi，k+j)，(gi，2k+j)，(gi，vj)，i=1，2，3，j=3，4，...，k-1 依次都可形成 Z3- 可收缩子图G1(引理1中的G1)，把它们依次收缩成一点，仍记为 v，此时 v 与(gi，k)，(gi，2k)，(gi，3k)，i=2，3 都形成 2- 圈，则(gi，k)，(gi，2k)，(gi，3k)，(gi，vk)，i=1，2，3 都可收缩到 v，因此 Jk× G∈＜Z3＞。

(iii)当 m=2l+1，l≥2，记 V(G)={g1，g2，g3，...，g2l+1}，如同(ii)的操作，使得点(g1，v1)与(g1，1)，(g1，k+1)，(g1，2k+1)，(g2，v1)形成以(g1，v1)为中心的W4，把这个W4收缩成一点，记为v，这时 v与点(g2，k+1)都形成2-圈，把(g2，k+1)收缩到 v，则 v 与(g3，k+1)相邻，同时v 与点(g1，2)，(g1，2k+2)，(g3，v1)，(g2l+1，1)，(g2l+1，k+1)，(g2l+1，2k+1)，(g2l+1，v1)都相邻，使用类似的方法，依次去掉边((gj，1)，(gj，k))，((gj，k)，(gj，vk))，((gj，vk)，(gj，3k))，((gj，3k})，(gj，k+1))，添加边((gj，1)，(gj，k+1));去掉边((gj，k+1)，(gj，k+2))，((gj，k+2)，(gj，k+3))，...，((gj，2k-1)，(gj，2k))，((gj，2k)，(gj，2k+1))，添加边((gj，k+1)，(g1，2k+1));去掉边((gj，1)，(gj+1，1))，((gj+1，1)，(gj+1，v1))，添加边((gj，1)，(gj+1，v1));去掉边((gj，2k+1)，(gj+1，2k+1))，((gj+1，2k+1)，(gj+1，v1))，添加边((gj，2k+1)，(gj+1，v1));其中 j=3，5，7，...，2l-1，使得点(gj，v1)与(gj，1)，(gj，k+1)，(gj，2k+1)，(gj+1，v1)形成以(gj，v1)为中心的W4，依次把这样的W4收缩成一点，记为v＇，则 v 与 v＇形成 2- 圈，因为 v 与(gj，k+1)，(gj，v1)，j=3，5，7，...，2l-1 都相邻，则可把这样的 v＇收缩到 v，则 v 与点(gn，k+1)，n=2，4，...，2l都形成2-圈，把这些2-圈都收缩到 v，则 v 与(gn，1)，(gn，2k+1)，(gn，3k)，n=2，4，...，2l都相邻，同时 v与点(g2l+1，v1)形成 2- 圈，由前知，v 与(g2l+1，1)，(g2l+1，k+1)，(g2l+1，2k+1)，(g2l+1，v1)都相邻，因此(g2l+1，1)，(g2l+1，k+1)，(g2l+1，2k+1)，(g2l+1，v1)都可收缩到 v，得到 v 与(g2l+1，k)相邻，则 v 与(gi，2)，(gi，k+2)，(gi，2k+2)，(gi，v2)，i=1，2，...，2l+1 形成Z3-可收缩子图G2(引理1中的G2)，把它收缩成一点，仍记为 v，则 v 与点(gn，1)，(gn，2k+1)，n=2，4，...，2l都形成 2- 圈，把这些 2- 圈都收缩到 v，则 v 与点(gn，k)，(gn，2k)，(gn，3k)，(n=2，4，...，2l)都相邻，类似的 v 与(gi，j)，(gi，k+j)，(gi，2k+j)，(gi，vj)，i=1，2，...，2l+1，j=3，4，...，k-1依次都形成 Z3-可收缩子图G2(引理1中的G2)，把它们依次收缩成一点，仍记为v，则 v 与(gn，k)，(gn，2k)，(gn，3k)，(n=2，4，...，2l)以及(g2l+1，k)，(g2l+1，2k)，(g2l+1，3k)都形成2- 圈，所以(gi，k)，(gi，2k)，(gi，3k)，(gi，vk)，i=1，2，...，2l+1 也都可收缩到 v，因此 Jk× G∈＜Z3＞。

(iv)当 m=2l，l≥2，记 V(G)={g1，g2，g3，...，g2l}，如同(iii)的操作，在第 1，3，...，2l-3个Jk-层进行同样的操作，同时在第2l个Jk-层也进行同样的操作后，则v与点(g2l-1，v1)形成2- 圈，v 与(g2l-1，1)，(g2l-1，k+1)，(g2l-1，2k+1)都相邻，同时 v 与点(gn，k+1)，(n=2，4，...，2l-2)都形成 2- 圈，则可把(gn，k+1)，(n=2，4，...，2l-2)，(g2l-1，v1)，(g2l-1，1)，(g2l-1，k+1)，(g2l-1，2k+1)依次都收缩到 v，则 v 与(gi，2)，(gi，k+2)，(gi，2k+2)，(gi，v2)，i=1，2，...，2l形成Z3-可收缩子图G3(引理1中的G3)，把它收缩成一点，仍记为 v，则 v 与(gn，1)，(gn，2k+1)，n=2，4，...，2l-2 都形成 2- 圈，因此(gn，1)，(gn，2k+1)，n=2，4，...，2l-2 都可收缩到v，则 v 与(gn，2k)，n=2，4，...，2l-2 都相邻，而v 与(gi，j)，(gi，2k+j)，(gi，vj)，(gi，k+j)，i=1，2，...，2l，j=3，4，...，k-1 依次都形成 Z3- 可收缩子图W2l，因此依次把它们都收缩到v，这时v与(gi，k)，(gi，3k)，i=1，2，...，2l形成 Z3- 可收缩子图 W2l，把它们也都收缩到 v，则 v与(gn，vk)，n=2，4，...，2l-2 都形成 2- 圈，把它们也都收缩到 v，则 v 与(gn，2k)，n=2，4，...，2l-2以及(g2l-1，2k)也都形成2-圈，再把它们也都收缩到 v，这时(gp，vk)(gp，2k)，p=3，5，...，2l-3都可收缩到 v，则此时 v 与(g1，vk)，(g2l，vk)，(g1，2k)，(g2l，2k)形成 Z3- 可收缩子图 W4，所以 Jk×G∈＜Z3＞。

由上述(i)(ii)(iii)(iv)命题得证。

［1］ Bondy，J.A.，Murty ，U.S.R..graph Theory with Applications［M］.New york:American Elsevier，1976

［2］ F.Jaeger，N.Linial.C.Payan，M.Tarsi.Group connectivity of graphs-a nonhomogeneons analogue of nowhere-zero flowproperties［J］.Comb.Theory，Ser.B，1992，56(2):165-182

［3］ Kochol，M.An equivalent version of the 3-flow conjecture［J］.Combin.Theory Ser.B，2001，83(2):258-261

［4］ Zhang ，C.Q..Integer flows and cycle covers of graphs［M］.New york:Marcel Dekker，1997

［5］ H.J.Lai.group connectivity of 3-edge-connected chordal graphs［J］.Graphs and Combinatorics，2000，16(2):165-176

［6］ M.Devos，R.Xu，G.Yu.Nowthere-zero Z3-flows through Z3-connectivity［J］.Discrete Math，2006，306(1):26-30

［7］ H.J.Lai.Nowthere-zero 3-flows in locally connected graphs［J］.Graph Theory，2003，42(3):211-219

Group Connectivity of The Cartesian Product on The Snark And a k-Circuit

GE Guoju1，WANG Tao2

(1.Department of Mathematics，Chaohu College，Chaohu Anhui238024;2.North China Institute of Science and Technology，Yanjiao Beijing-East101601)

In this paper，by reduction methods proved that the Cartesian product graph Jk×Cm，m≥2 is Z3-connectivity.

Cartesian product;group-connectivity;contraction

O157.5

A

1672-7169(2011)03-0074-04

2011-04-23。基金项目:中央高校基本科研业务费资助(2011B019)。

葛国菊(1981-)，女，安徽含山人，硕士，安徽巢湖学院教师，研究方向:图论。