葛國菊 王 濤

(1.巢湖學(xué)院數(shù)學(xué)系，安徽巢湖 238024;2.華北科技學(xué)院基礎(chǔ)部，北京東燕郊 101601)

一類Snark與k-圈的卡式積圖的連通性①

葛國菊1②王 濤2

(1.巢湖學(xué)院數(shù)學(xué)系，安徽巢湖 238024;2.華北科技學(xué)院基礎(chǔ)部，北京東燕郊 101601)

本文主要運(yùn)用約化的方法證明了Flower snark Jk與Cm的卡式積圖Jk×Cm是Z3-連通的。

卡式積;群連通;收縮

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。由于Jk×Cm，m≥2為5-正則圖，且當(dāng)m≥5時(shí)，Jk×Cm為5-邊連通的5-正則圖，因此根據(jù)猜想2它應(yīng)該是Z3-連通的。從而，旁證了以上兩個(gè)猜想。本文主要用約化的方法證明了Jk×Cm，m≥2是Z3-連通的。本文中的圖都是指無環(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?；舅枷敕椒ㄔ冢?］中有介紹。

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:對(duì)奇整數(shù) k，k≥3，F(xiàn)lower snark Jk結(jié)構(gòu)如下:

V(Jk)={v1，v2，...，vk}∪{1，2，...，k，k+1，k+2，...，2k，2k+1，2k+2，...，3k}，圖 Jk有4k 個(gè)頂點(diǎn)，是由一個(gè) k 長圈1，2，...，k，1 和一個(gè)2k 長圈 k+1，k+2，...，2k，2k+1，2k+2，...，3k，k+1 組成，另外添加頂點(diǎn) vi(i=1，2，...，k)與i，k+i和 2k+i都相鄰。例如 J5，J7的圖如下:

定理1:G=Cm，m≥2的整數(shù)，則 Jk×G∈＜Z3＞。

為了證明這個(gè)定理，我們先看一個(gè)引理。

引理1設(shè) G1，G2，G3滿足下列條件，則 G1，G2，G3都是 Z3- 連通的。

(1)G1是由 K1，3× C3和點(diǎn) v 組成，設(shè) V(K1，3)={v1，1，2，3}，V(C3)={g1，g2，g3}，且在 G1中 v與點(diǎn)(g1，1)，(g1，3)，(g2，2)，(g3，1)，(g3，2)，(g3，3)相鄰。

(2)G2是由 K1，3× C2l+1和點(diǎn) v 組成，設(shè) V(K1，3)={v1，1，2，3}，V(C2l+1)={g1，g2，...，g2l+1}，且在 G2中 v 與點(diǎn)(gi，1)，(gi，3)，(gj，2)，i=1，3，...，2l+1，j=2，4，...，2l，2l+1 都相鄰。

(3)G3是由 K1，3× C2l和點(diǎn) v 組成，設(shè) V(K1，3)={v1，1，2，3}，V(C2l)={g1，g2，...，g2l}，且在 G3中 v 與點(diǎn)(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-圈，又因?yàn)?v與點(diǎn)(g3，3)相鄰，所以點(diǎn)(g1，3)，(g2，3)，(g3，3)依次都可收縮到 v，則 v 與點(diǎn)(g2，v1)，(g3，v1)都相鄰，又因?yàn)?v與點(diǎn)(g2，2)，(g3，2)相鄰，所以 v 與點(diǎn)(g2，v1)，(g3，v1)，(g2，2)，(g3，2)形成 W4，則(g1，v1)，(g2，v1)，(g3，v1)，(g1，2)，(g2，2)，(g3，2)都可收縮到v，這時(shí)v 與(g3，1)形成2-圈，v 與點(diǎn)(g2，1)相鄰，因此(g1，1)，(g2，1)，(g3，1)依次也都可收縮到 v，根據(jù)命題1(5)知，G1∈ ＜Z3＞。

(2)去掉邊(v，(g1，1))，((g1，1)，(g1，v1))，((g1，v1)，(g1，3))，添加邊(v，(g1，3))，則v與(g1，3)形成2-圈，又因?yàn)?v與點(diǎn)(g2l+1，3)相鄰，所點(diǎn)(g1，3)，(g2l+1，3)都可收縮到 v，則 v 與點(diǎn)(g2，3)，(g2l，3)，(g2l+1，v1)都相鄰，再去掉邊(v，(g2l+1，2))，((g2l+1，2)，(g2l+1，v1))，添加邊(v，(g2l+1，v1))，則點(diǎn)(g2l+1，v1)，(g2l+1，1)依次可收縮到 v，則 v 與點(diǎn)(g2l，v1)，(g2l，1)都相鄰，再去掉(v，(g2l-1，3))，((g2l-1，3)，g2l-1，v1)，添加邊(v，(g2l-1，v1))，則 v 與點(diǎn)(g2l，v1)，(g2l-1，v1)，(g2l，1)，(g2l-1，1)形成 W4，把它收縮到 v，則點(diǎn)(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，此時(shí) 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，這時(shí) v 與(g2l-1，3)也形成2-圈，根據(jù)命題1(5)知，G2∈＜Z3＞。

(3)去掉邊(v，(g1，1))，((g1，1)，(g1，v1))，((g1，v1)，(g1，3))，添加邊(v，(g1，3))，則v與(g1，3)形成 2- 圈，又因?yàn)?v 與點(diǎn)(g2l-1，3)，(g2l，3)相鄰，所以點(diǎn)(g1，3)，(g2l，3)，(g2l-1，3)都可收縮到 v，則 v 與點(diǎn)(g2l，v1)，(g2l-1，v1)都相鄰，又因?yàn)?v 與點(diǎn)(g2l，1)，(g2l，1)相鄰，所以 v 與點(diǎn)(g2l，v1)，(g2l-1，v1)，(g2l，1)，(g2l-1，1)形成W4，把它收縮到 v，則點(diǎn) (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，根據(jù)命題1(5)知，G3∈＜Z3＞。

證明定理1(i)當(dāng)m=2時(shí)，命題顯然成立;

(ii)當(dāng) m=3時(shí)，記 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)是中心，把這個(gè) W4收縮成一點(diǎn)，記為 v，這時(shí) v與點(diǎn)(g2，k+1)，(g3，v1)都形成 2- 圈，v 與點(diǎn)(g1，2)，(g1，2k+2)相鄰，同時(shí) v 與(g3，1)，(g3，k+1)，(g3，2k+1)都相鄰，因此把點(diǎn)(g2，k+1)，(g3，v1)，(g3，1)，(g3，k+1)，(g3，2k+1)依次收縮到 v，此時(shí) v 點(diǎn)(g2，1)，(g2，k+2)，(g2，2k+1)，(g2，3k)都相鄰，同時(shí) v 與(g3，2)，(g3，k+2)，(g3，2k+2)，(g3，k)，(g3，2k)，(g3，3k)也都相鄰，此時(shí) v 與(gi，2)，(gi，k+2)，(gi，2k+2)，(gi，v2)，i=1，2，3 形成 Z3- 可收縮子圖 G1(引理1中的G1)，把它收縮成一點(diǎn)，仍記為v，這時(shí) v 與點(diǎn)(g2，1)，(g2，2k+1)都形成 2- 圈，則點(diǎn)(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)，把它們依次收縮成一點(diǎn)，仍記為 v，此時(shí) 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)當(dāng) m=2l+1，l≥2，記 V(G)={g1，g2，g3，...，g2l+1}，如同(ii)的操作，使得點(diǎn)(g1，v1)與(g1，1)，(g1，k+1)，(g1，2k+1)，(g2，v1)形成以(g1，v1)為中心的W4，把這個(gè)W4收縮成一點(diǎn)，記為v，這時(shí) v與點(diǎn)(g2，k+1)都形成2-圈，把(g2，k+1)收縮到 v，則 v 與(g3，k+1)相鄰，同時(shí)v 與點(diǎn)(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，使得點(diǎn)(gj，v1)與(gj，1)，(gj，k+1)，(gj，2k+1)，(gj+1，v1)形成以(gj，v1)為中心的W4，依次把這樣的W4收縮成一點(diǎn)，記為v＇，則 v 與 v＇形成 2- 圈，因?yàn)?v 與(gj，k+1)，(gj，v1)，j=3，5，7，...，2l-1 都相鄰，則可把這樣的 v＇收縮到 v，則 v 與點(diǎn)(gn，k+1)，n=2，4，...，2l都形成2-圈，把這些2-圈都收縮到 v，則 v 與(gn，1)，(gn，2k+1)，(gn，3k)，n=2，4，...，2l都相鄰，同時(shí) v與點(diǎn)(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)，把它收縮成一點(diǎn)，仍記為 v，則 v 與點(diǎn)(gn，1)，(gn，2k+1)，n=2，4，...，2l都形成 2- 圈，把這些 2- 圈都收縮到 v，則 v 與點(diǎn)(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)，把它們依次收縮成一點(diǎn)，仍記為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)當(dāng) m=2l，l≥2，記 V(G)={g1，g2，g3，...，g2l}，如同(iii)的操作，在第 1，3，...，2l-3個(gè)Jk-層進(jìn)行同樣的操作，同時(shí)在第2l個(gè)Jk-層也進(jìn)行同樣的操作后，則v與點(diǎn)(g2l-1，v1)形成2- 圈，v 與(g2l-1，1)，(g2l-1，k+1)，(g2l-1，2k+1)都相鄰，同時(shí) v 與點(diǎn)(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)，把它收縮成一點(diǎn)，仍記為 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，這時(shí)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，這時(shí)(gp，vk)(gp，2k)，p=3，5，...，2l-3都可收縮到 v，則此時(shí) 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?；痦?xiàng)目:中央高?；究蒲袠I(yè)務(wù)費(fèi)資助(2011B019)。

葛國菊(1981-)，女，安徽含山人，碩士，安徽巢湖學(xué)院教師，研究方向:圖論。