哈密頓分解

哈密頓分解（也稱為 Hamiltonian 分解；Bosák 1990, p. 123）是指將哈密頓正則圖的邊集劃分為哈密頓環。上圖展示了五胞體圖 的六種不同的哈密頓分解。

該定義有時會擴充套件到將偶數度正則圖分解為哈密頓環，或將奇數度正則圖分解為哈密頓環和一個完美匹配（Alspach 2010），後一種型別的分解被稱為準哈密頓分解（quasi-Hamilton decomposition）（Bosák 1990, p. 123）。

對於三次圖，哈密頓分解等價於單個哈密頓環。對於四次圖，哈密頓分解等價於一個哈密頓環 ，移除該環的邊後會留下一個連通圖。當這個連通圖存在時，它給出了構成哈密頓分解 的一對哈密頓環中的第二個環 。對四次圖的所有哈密頓環迭代此過程會生成每個哈密頓分解兩次，對應於兩種不同的排序 和 。

在 19 世紀 90 年代，Walecki 證明了完全圖 當 為奇數時，允許哈密頓分解；當 為偶數時，允許分解為哈密頓環加上一個完美匹配（Lucas 1892, Bryant 2007, Alspach 2008）。

1954 年，Ringel 證明了當 是 2 的冪時，超立方體圖 允許哈密頓分解（Alspach 2010）。Alspach et al. (1990) 證明了每個 對於 都允許哈密頓分解。

Laskar 和 Auerbach (1976) 證明了完全二部圖 在度數為偶數時具有（真）哈密頓分解。事實上， 具有真哈密頓分解當且僅當 且 為偶數時；具有準哈密頓分解當且僅當 且 為奇數時（Bosák 1990, p. 124）。更一般地，完全 部圖 ，其中 ，具有哈密頓[準哈密頓]分解當且僅當 且 為偶數[奇數]時（Bosák 1990, p. 124）。

Alspach et al. (2012) 證明了 Paley 圖允許哈密頓分解。

Kotzig (1964) 證明了三次圖是哈密頓圖當且僅當它的線圖具有哈密頓分解時（Bryant 和 Dean 2014）。

找到非哈密頓可分解的正則哈密頓非頂點傳遞圖並不太難，如上面的例子所示。

要描述非哈密頓可分解的正則哈密頓頂點傳遞圖則更為困難。S. Wagon（私人通訊，2013 年 2 月；Dupuis 和 Wagon 2014）曾推測，所有連通頂點傳遞圖都是哈密頓可分解的，但以下情況除外：、、、、 和 。其中， 表示 Petersen 圖， 表示 Coxeter 圖， 表示 的三角形替換圖， 表示 的線圖。根據 Kotzig (1964) 的定理，Bryant 和 Dean (2014) 將 新增到此列表。因此，該猜想可以更簡單地表述為：“除了 和 之外，每個哈密頓頂點傳遞圖都具有哈密頓分解”，該猜想已在節點數不超過 的情況下得到驗證。（可以用 H-*-連通圖來對該猜想進行稍微更通用和精確的陳述。）

然而，Bryant 和 Dean (2014) 反駁了該猜想，他們證明存在無限多個沒有哈密頓分解的連通頂點傳遞圖，其中包括無限多個頂點度為 6 的圖，以及頂點度數任意大的Cayley 圖。反例來自於將三角形替換圖推廣到 替換 正則圖，最小的反例是由從立方圖 的邊加倍得到的多重圖獲得的 替換圖給出。一般來說， 和 是反例，其中 表示透過取 份 的邊而得到的多重圖，， 表示對 進行 頂點替換操作，並且 是 Möbius-Kantor 圖（Bryant 和 Dean 2014）。