凱勒圖

n 維凱勒圖，有時記為 (例如，Debroni et al. 2011)，可以定義在 個元素的頂點集 上，其中每個 為 0、1、2 或 3，並且當兩個頂點在至少兩個座標上不同，且在至少一個位置標籤的差為 2（模 4）時，它們是相鄰的。

這些圖為凱勒猜想提供了一個方便的圖論公式，並被廣泛用於測試最大團演算法（Myrvold 和 Fowler，Debroni 2011），因為即使對於 ，大多數啟發式團演算法也達不到正確的最大團階數。

Corrádi 和 Szabó (1990) 表明，此圖中的團的大小最多為 ，並且進一步表明，如果存在大小為 的團，則凱勒猜想在該維度上是錯誤的。然而，請注意，這種團的不存在並不一定意味著猜想的正確性，僅意味著對於座標為整數或半整數的超立方體不存在反例（Debroni et al. 2011）。透過數學證明（Perron 1940），已知凱勒猜想對於 是成立的，並且對於至少 、10 和 12 是錯誤的，最小的未解決情況是 ，其中維度 的反證是透過構造大小為 的最大團來實現的。最近，Debroni et al. (2011) 確定了 團數 為 為 124，但是，如上所述，大小為 的團的缺失並不能在維度 中確立該定理。

凱勒圖 (n=1, 2, ...) 的團數由 1, 2, 5, 12, 28, 60, 124, 256, ... 給出 (OEIS A202604)。

對於 ，凱勒圖 的色數、分數色數和獨立數均為 (W. Myrvold; 私人通訊，S. Wagon，2013 年 1 月 22 日)。對於 , 2, ...，獨立數明確地為 4, 5, 8, 16, 32, 64, 128, 256, ... (OEIS A258935)。

Jarnicki et al. 2017 表明，所有凱勒圖都是 1 類圖，即邊色數等於它們的最大頂點度 。

Fung (2011) 給出了凱勒圖 , , ... 的 Lovász 數，分別為 4、6、28/3、、、....

所有連通的凱勒圖都是哈密頓圖 (W. Myrvold; 私人通訊，S. Wagon，2013 年 1 月 23 日) 和 哈密頓連通圖 (私人通訊，S. Wagon，2013 年 1 月 24 日)。

特殊情況總結在下表中，其中 2-凱勒圖（同構於 Clebsch 圖）的情況的構造在上面進行了說明。

	圖
1	4-空圖
2	克萊布什圖