去3 度點的Pósa- 條件的性質研究*

張岳

（海南廣播電視大學，海南 海口570208）

1 概述

本文中所涉及的圖均為有限圖，未明確給出的定義和概念均以[1]中為準。令D是一個定向圖，A是一個阿貝爾群（“0”為單位元的加法群），φ：E（D）→A 是一個函數，如果0?φ（E（D）），則稱φ 是處處不為零的。對每個頂點ν∈V（D），設函數?φ：V（D）→A 為?φ（ν）=∑e∈E+（ν）φ（e）-∑e∈E-（ν）φ（e）且有∑v∈V（D）?φ（ν）=0。如果?φ 的值恒等于零，則稱φ 為流或A- 流。之后Jaeger 等人[2]在研究和推廣流的問題過程中又引入了群連通的概念。如果對于每個滿足∑ν∈V（D）P（ν）=0 的函數p：V（D）→A，總能找到處處不為零的函數φ：E（D）→A使得?φ=p，則稱D是A- 連通的。

在[3]中，給出了一個處處不為零的流的存在性并不依賴于邊的定向，接下來我們只討論無向圖的群連通性。

在[6] 中，Zhang和Yin 給出了滿足Pósa- 條件的圖是否Z3-連通的一個充分條件，但是d1=d2=3 的情況并沒有解決。在本文中，將討論滿足Pósa- 條件的圖去掉3 度點后是否還滿足Pósa- 條件，這將對今后討論d1=d2=3 時滿足Pósa- 條件的圖是否Z3- 連通奠定基礎。

2 主要結論

定理2 設G是n 階簡單圖（n≥9），G滿足Pósa- 條件，π（G）=（d1，d2，Λdn），其中3=d1≤d2≤Λ≤dn，V（G）={v1，v2，Λ，vn}且dG（vi）=di（i=1，2，Λ，n）。設G*=G-v1，NG（v1）={vp，vq，vs}（p＜q＜s），則G*不滿足Pósa- 條件當且僅當G屬于以下四種情況。

證明：設π（G*）=（d1*，d2*，Λdn-1*），其中d1*≤d2*≤Λ≤dn-1*。設lG*（v）表示dG*（v）在π（G*）中的位置序號，其中v≠v1。我們考慮以下兩種情況。

情形1 n 是偶數