pósa-條件下的圖的 Z4-連通性

張 岳,尹建華

（海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南?？?570228）

pósa-條件下的圖的 Z4-連通性

張 岳,尹建華

（海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南?？?570228）

一個(gè)滿足 pósa-條件且階至少為 3的簡單圖G是A-連通的當(dāng)且僅當(dāng)G≠C4,其中A是階至少為 4的阿貝爾群.

pósa-條件;群流;群連通性

為了給出圖的群連通性定義,先給出圖的一些基本概念.本文中所涉及的圖均為有限圖,且可以包含多重邊和環(huán).圖G的頂點(diǎn)集和邊集分別記作V（G）和E（G）.若一個(gè)圖不包含多重邊和環(huán),則稱之為簡單圖.設(shè)D是無向圖G的一個(gè)定向且v?V（G）,則用E+（v）（或E-（v））表示以v為尾（或頭）的邊構(gòu)成的集合.n階循環(huán)群記作Zn,其中n≥2.設(shè)V1,V2是V（G）的 2個(gè)不相交的子集,e（V1,V2）表示一個(gè)頂點(diǎn)在V1中另一個(gè)頂點(diǎn)在V2中的邊的個(gè)數(shù).

令D是一個(gè)定向圖,A是一個(gè)阿貝爾群（“0”為單位元的加法群）,φ:E（D）→A是一個(gè)函數(shù),如果 0φ（E（D））,則稱φ是處處不為零的.對(duì)每個(gè)頂點(diǎn)vV（D）,設(shè)函數(shù) ?φ:V（D）→A為 ?φ（v）=∑ φ（e）-

e∈E+（v）∑e∈E-（v）φ（e）且有 ∑v∈V（D）?φ（v）=0.如果 ?φ的值恒等于零,則稱φ為流或A-流.如果對(duì)于每個(gè)滿足∑v∈V（D）p（v）=0的函數(shù)p:V（D）→A,總能找到處處不為零的函數(shù)φ:E（D）→A使得 ?φ=p,則稱D是A-連通的.

如果φ是D中的一個(gè)處處不為零的流,則對(duì)D中任意一條邊e,將e的方向反向,用 -φ（e）替換φ（e）,所得到的仍然是D中的一個(gè)處處不為零的流.由此可見一個(gè)處處不為零的流的存在性并不依賴于邊的定向,而只與原來的無向圖有關(guān).因此,如果無向圖G的某個(gè)定向有處處不為零的A-流 （是A-連通的）,則稱G有處處不為零的A-流（是A-連通的）.因此,接下來只討論無向圖的群連通性.

群連通的概念是由 Jaeger等人[2]在研究和推廣流的問題過程中引入的.在文獻(xiàn)[2]中,有如下猜想:

猜想 1[2]:任何一個(gè) 5-邊連通圖都是Z3-連通的.

猜想 2[2]:任何一個(gè) 3-邊連通圖都是Z5-連通的.

上述 2個(gè)猜想蘊(yùn)含著 Tutte的著名的 3-流猜想和 5-流猜想.

1）pósa-條件包含Ore-條件,反之不成立.

2）如果G滿足 pósa-條件,則G是哈密頓圖,G有一個(gè)處處不為零的 4-流,但G不一定是Z4-連通的.

令A(yù)是階至少為4的阿貝爾群.在文獻(xiàn)[4]中,Sun J Z等人證明了一個(gè)滿足Ore-條件且階至少為3的簡單圖G是A-連通的當(dāng)且僅當(dāng)G≠C4.在本文中將進(jìn)一步證明一個(gè)滿足 pósa-條件且階至少為 3的簡單圖G是A-連通的當(dāng)且僅當(dāng)G≠C4,見定理 1.

1 主要結(jié)論

設(shè)G是一個(gè)圖,X?E（G）.在G中將集合X中的每條邊e的 2個(gè)頂點(diǎn)重合,然后去掉邊e所得到的圖稱為G收縮X,記為G/X.為簡單起見,把G/{e}記作G/e,把G/E（H）記作G/H.為了證明主要結(jié)論,首先給出下面幾個(gè)引理.

引理 1[3]設(shè)A是一個(gè)阿貝爾群,H是G的子圖.如果H和G/H都是A-連通的,則G也是A-連通的.

引理 2 設(shè)A是一個(gè)阿貝爾群.有下面幾個(gè)結(jié)論

定理 1 設(shè)|G|=n≥3.如果G滿足 pósa-條件,則G是A-連通的當(dāng)且僅當(dāng)G≠C4,其中A是階至少為 4的阿貝爾群.

證明 如果G是A-連通的,則根據(jù)引理 2中的結(jié)論1）,G≠C4.反之,如果G≠C4,將證明G是A-連通的.當(dāng)n=3時(shí),G顯然是一個(gè)三角形,根據(jù)引理 2中的結(jié)論 1）,G是A-連通的.接下來假設(shè)n≥4,根據(jù)G是否包含三角形來分 2種情況討論.

情況 1G包含三角形.

[1]CHEN J J,ESCHEN E,LA IH J.Group connectivity of certain graphs[J].Ars Combin.,2008,89:141-158.

[2]JAEGER F,L IN IAL N,PAYAN C,et al.Group connectivity of graphs-A nonhomogeneous analogue of nowhere zero flow properties[J].J.Combin.,Theory Ser.B,1992,56:165-182.

[3]LA IH J.Group connectivity of 3-edge-connected chordal graphs[J].Graphs Combin.,2000,16:165-176.

[4]SUN J Z,XU R,Y IN J H.Group connectivityof graphs satisfyingOre-condition:proceeding 2008 InternationalConference on Foundations of Computer Science,LasVegas,July 14-17,2008[C].USA:Csrea Press,2008:21-24.

Z4-connectivity of Graphs Satisfying pósa-condition

ZHANG Yue,Y IN Jian-hua

（College of Information Science and Technology,Hainan University,Haikou 570228,China）

In this paper,a simple graphGsatisfying pósa-condition withV（G）≥3 isA-connected if and only ifG≠C4was showed,in whichAis an abelian group andC4is a cycle of length 4.

pósa-condition;group flow;group connectivity

O 157.5

A

1004-1729（2010）03-0209-03

2010-04-06

國家自然科學(xué)基金項(xiàng)目 （10861006）

張?jiān)溃?986-）,女,河北邢臺(tái)人,海南大學(xué)信息科學(xué)技術(shù)學(xué)院應(yīng)用數(shù)學(xué) 2008級(jí)碩士研究生.

尹建華 （1970-）,男,湖南祁陽人,海南大學(xué)信息科學(xué)技術(shù)學(xué)院應(yīng)用數(shù)學(xué)系教授,博士.