圖中含有控制圈的一個充分條件

摘 要:本文證明了:設是階且圍長的連通圖，是2-連通的。如果對任意邊，，有，則中含有一個控制圈。

關鍵詞:控制圈邊度圍長控制邊

中圖分類號:O157文獻標識碼:A文章編號:1674-098X(2011)05(b)-0254-01

1 引言

設表示圖中所有圈構成的集合。如果而且，則稱是的一個控制圈。

設，端點分別在和中的最短路的長度稱為和的距離，記為。

如果且，，則稱和是鄰近的。若且和鄰近，則稱和分離的。對于，定義的度。對于，設至少有一個端點在中}，記。

設是的確定了一個方向的圈或道路，對于，在上沿著的方向，的前繼點記為，的后繼點記為。對于，，

記。對于圖，用表示圖的圍長，即最短圈的長度。

定義且。

Veldman在文獻[3]中給出了如下結論:

定理1[3] 設是階非樹圖，如果對中任意一對分離的邊，

有，則中含有一個控制圈。

劉春峰在[4]和[5]中得到:

定理2[4]

設是階連通圖，且是2-連通的，如果對任意邊，，有，則G中含有一個控制圈。

定理3[5]

設是階連通圖，且是2-連通的，如果對中任意一對分離的邊，有，則中含有一個控制圈。

本文在適當增加圖的圍長的情況下，改進了原有的一些結果。

2 主要結論和證明

定理:設圖是階且圍長的連通圖，是2-連通的。如果對任意邊，

，有，則中含有一個控制圈。

證明用反證法，假設圖中不含有控制圈。

因為是2-連通的，所以。

因此，我們可選取，使得最大。

設且規定下標次序的方向為正向。

因為中不含控制圈而且是連通圖，所以必存在且與上某點鄰近。

不妨設，設，，，

因為，所以，否則中含有長度比9小的圈。

又由邊的選擇知，。

令，

。

因為映射:是到自身的一一對應，所以()。

因為

，所以，()()。

而由可知:

，否則中含有三角形。

，否則中含有5-圈。

，否則中含有6-圈。

，否則中含有7-圈。

，否則中含有8-圈。

而由和前繼點的定義可知，。

因此，除

外，

()兩兩互不相交。

令，

易知。

因為的圍長是，

所以()。

()。

于是

＝

而，這與定理的條件矛盾，所以假設不成立。

即中必含有一個控制圈。

參考文獻

[1]Bondy J A，Murty U S R. Graph Theory with Applications[M].Amsterdam: Elsevier North-Holland， 1976.

[2]Harary F，Nash-Williams.CstJA，On Eulerian and Hamliton graph and line graph[J].Canada.Math.Bull，1965(8):701～710.

[3]Veldman H.J.Existence of Dominating Cycles and Path[J].Discrete Math，1983，(43):281～29.

[4]劉春峰.關于圖中的控制圈[J].渝州大學學報，1989(11):13～15.

[5]劉春峰.關于圖中控制圈的一點注記[J].錦州工學院學報，1989(3):164～167.