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 日)。