[科普中國]-泛圈圖

泛圈圖(pancyclic graph)是一個特殊的哈密頓圖。具體地說，若在一個n階圖G上存在長度分別為3，4，…，n的圈，則稱該圖為泛圈圖。若對于G上任何一節(jié)點v，在G中都存在長度分別為3，4，…，n的圈通過v，則稱G為點泛圈圖。若對于圖G上任何一條邊e，在G上都存在長度分別為3，4，…，n的圈通過e，則稱G為邊泛圈圖。設(shè)G是一個二部圖，因為在G中沒有奇長圈，所以不會是泛圈的。若在G上存在長度為4，…，n-2，n(n偶數(shù))的圈，則稱它是泛偶圈的.類似地，定義點泛偶圖和邊泛偶圈1。

定義**(Hakimi和Schmeichel定理)** n階簡單圖的非降次序列 滿足條件：

則是泛圈圖(pancycle graph)或為二分圖，泛圈圖指圖內(nèi)存在長度為 的圈。泛圈圖是由Bondy在1971年引入的2。

相關(guān)定理定理1 (Bondy定理) 階簡單圖滿足條件： 且 有

則是泛圈圖或 。

定理2設(shè)是一個度序列為的階圖。如果對于每一個滿足的正整數(shù)，有，則G要么是泛圈的，要么是偶圖3。

證明： 首先假設(shè)是奇數(shù)，則，因為要么，這種情況下的結(jié)果是明顯的；要么，這種情況下由假設(shè)，再由Chvátal定理知G是H圖。

推論3設(shè)G是一個階數(shù)為的圖，如果對G中每一對不相鄰的頂點，有，則G要么是泛圈的，要么是圖。

定理4 設(shè)G是一個連通度為、獨立數(shù)為的圖，并且假設(shè)。若存在一個數(shù)c，使得如果G至少有個頂點，則G是泛圈的。

對于的情況，Bondy已經(jīng)證明了結(jié)果。

定理5若G是一個連通圖，那么

(1) 是一個泛圈圖；

(2) 如果是Hamilton的，則是泛圈的；

(3) 如果G是一個2連通的，則是泛圈的。

泛圈的概念也已被引入到有向圖。一個階有向圖D稱為是泛圈的，如果對于每個滿足的正整數(shù)，在D中含有長度為的有向圈。顯然，每個泛圈有向圖是Hamilton的。Moon已經(jīng)證明了每個強連通的競賽圖是泛圈。

定理6強階競賽圖的每一個頂點被包含在一個長度為k的圈中．其中。

本詞條內(nèi)容貢獻(xiàn)者為:

孫和軍 - 副教授 - 南京理工大學(xué)