Hamilton-Laceable 圖

一個連通二部圖被稱為 Hamilton-laceable 圖，這個術語顯然由 Simmons (1978) 引入，如果對於所有頂點對 和 ，其中 屬於二劃分的一個集合，而 屬於另一個集合，它都存在 哈密頓路徑。

一個二部圖，如果其迂迴矩陣元素 對於所有 和 （對應於頂點二劃分的不同元素）都是最大的，那麼它就是 Hamilton-laceable 圖。

包括孤立點圖（通常認為它既是可追蹤的又是二部的），頂點數為 , 2, ... 的 Hamilton-laceable 圖的數量是 1, 1, 0, 1, 0, 2, 0, 12, 0, 226, 0, ... （OEIS A236219），其中前幾個示例如上所示。

由於從二劃分的一個集合中的一個頂點到另一個集合中的一個頂點的哈密頓路徑必須包含奇數條邊（即，邊的端點在二劃分的各部分之間交替），因此 Hamilton-laceable 圖的頂點數必須是偶數（除了退化情況 ）。 除了 之外，Hamilton-laceable 圖也是哈密頓圖，因為總能找到來自不同部分的兩個頂點 和 ，它們之間包含一條邊 ，Hamilton-laceable 的定義要求存在一條哈密頓路徑，從 開始到 結束，並且 將這條路徑的端點連線成一個哈密頓環。

並非所有偶數頂點數、二部、哈密頓圖都是 Hamilton-laceable 圖。例如，多米諾骨牌圖 有 6 個頂點，是哈密頓圖和二部圖，但不包含連線中間梯級的頂點的哈密頓路徑（這些頂點位於二劃分的不同部分）。頂點數為 , 4, ... 的這種圖的數量是 0, 0, 2, 12, 253, ....

Dupuis 和 Wagon (2014) 推測，除了 且 的偶圈圖之外，所有二部哈密頓頂點傳遞圖都是 Hamilton-laceable 圖。可以用 H-*-連通圖來對這個猜想做一個稍微更通用和精確的陳述。

假設 ，網格圖 是 Hamilton-laceable 圖，當且僅當 或者 中至少有一個是偶數且 。網格圖在三個或更多維度中是 Hamilton-laceable 圖，當且僅當它至少有一個偶數索引 (Simmons 1978)。

所有超立方體圖都是 Hamilton-laceable 圖，這個結果來源於 Chen 和 Quimpo (1981) 的研究結果。

馬步圖是 Hamilton-laceable 圖，當且僅當 , , 且 , 中至少有一個是偶數 (Dupuis 和 Wagon 2014)。

Pensaert (2002) 推測，對於 且 ，如果 是偶數且 是奇數，則廣義 Petersen 圖 是 Hamilton-laceable 圖，否則是 Hamilton-連通圖。

可以使用 Wolfram 語言中的預計算值來檢查一些常見圖的集合。GraphData[g, "HamiltonLaceable"].