McLaughlin 圖

McLaughlin 圖是一個 112-正則圖，具有 275 個節點和 條邊，可以從 Witt 設計構建。它是距離正則的，具有相交陣列 。它也是距離傳遞的。

McLaughlin 圖的第一個（同構於廣義四邊形 ）和第二個子構成圖也是距離正則的 (DistanceRegular.org)。

為了構建該圖，使用Witt 設計建立一個 276 節點圖 ，該圖不是正則的，但其切換類是一個正則二圖。（請注意，二圖不是圖，但等價於圖的切換類。切換類中的任何一個圖都確定了整個切換類。）圖 有兩種型別的頂點；Witt 設計的點和 Witt 設計的塊。圖 的兩個頂點 相鄰當且僅當以下條件之一成立

1. 是一個點， 是一個不包含 的塊

2. 和 是在一個點相交的塊。

這產生了一個 276 頂點的圖，其中每個“點”頂點的度為 176，每個“塊”頂點的度為 128。

它也可以從 Leech 格構建，方法是從形成邊長為 2、2 和 的等腰三角形頂點的三個格點開始，識別恰好 275 個與每個三角形頂點距離為 2 的格點，並將兩個點與一條邊連線，如果它們之間的距離為。結果圖是 McLaughlin 圖（Conway 和 Sloane 1999，第 292-293 頁；Gaucher 2013；Brouwer 和 van Maldeghem 2022，第 338 頁）。

正則二圖具有以下性質：如果我們取切換類中的一個圖，那麼我們可以“切換掉”任何頂點。考慮對應於點 0 的頂點 ；然後我們可以將剩餘的頂點分為三組： 是 176 個不包含 0 的塊， 是 22 個其他點 ， 是 77 個包含 0 的塊。

劃分 是 頂點的等分劃分。更準確地說，簡單的（有點）計數告訴我們

1. 頂點 與 中的 176 個頂點相鄰，與 中的 0 個頂點相鄰，與 中的 0 個頂點相鄰。

2. 中的任何頂點都與頂點 相鄰，與 中的 70 個（其他）頂點相鄰，與 中的 15 個頂點相鄰，與 中的 42 個頂點相鄰。

3. 中的任何頂點都與 中的 120 個頂點相鄰，與 中的 0 個頂點相鄰，與 中的 56 個頂點相鄰。

4. 中的任何頂點都與 中的 96 個頂點相鄰，與 中的 16 個頂點相鄰，與 中的 16 個頂點相鄰。

如果我們現在切換 的鄰域（即集合 ），那麼 的鄰居和非鄰居之間的每條邊都變成非邊，反之亦然。這樣做的效果是，從 到 、 到 、 到 的所有邊都變成非邊，並且從 到 、 到 、 到 的所有非邊都變成邊。特別是，

1. 變成一個孤立頂點（ 和 之間的所有邊都從邊變成非邊）

2. 中的每個頂點仍然與 中的 70 個頂點相鄰，但現在與 個 中的頂點和 個 中的頂點相鄰。

3. 中的每個頂點都與 個 中的頂點相鄰，仍然與 中的 0 個頂點相鄰，並且仍然與 中的 56 個頂點相鄰。

4. 中的每個頂點都與 個 中的頂點相鄰，並且仍然與 中的 16 個頂點和 中的 16 個頂點相鄰。

快速計算表明， 中每個頂點的度為 ， 中每個頂點的度為 ， 中每個頂點的度為 。因此，如果我們丟棄頂點 ，那麼剩下的就是在 276 個頂點上的 112-正則 McLaughlin 圖。

McLaughlin 圖的獨立數為 22 (Brouwer)，有 4050 個最大獨立頂點集 (Brouwer)，以及 個極大獨立頂點集 (R. Pratt，私人通訊，2011 年 12 月 11 日)。