泛圈圖

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

基本介紹

• 中文名：泛圈圖
• 外文名：pancyclic graph
• 屬性：一個特殊的哈密頓圖
• 提出者：Bondy
• 所屬問題：組合學(圖與超圖)

定義

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

則是泛圈圖(pancycle graph)或為二分圖，泛圈圖指圖記憶體在長度為 的圈。泛圈圖是由Bondy在1971年引入的。

相關定理

定理1 (Bondy定理) 階簡單圖滿足條件： 且 有

則是泛圈圖或 。

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

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

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

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

對於的情況，Bondy已經證明了結果。

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

(1) 是一個泛圈圖；

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

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

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

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