一个 -正则 简单图
在
个节点上是强
-正则的,如果存在正整数
、
和
,使得每个顶点有
个邻居(即,该图是一个 正则图),每对相邻顶点有
个共同邻居,并且每对不相邻顶点有
个共同邻居 (West 2000, pp. 464-465)。一个不是强正则的图被称为 弱正则。
一个 距离正则图,其 图直径 为 ,是一个强正则图 (Biggs 1993, p. 159)。因此,强正则图是 距离正则 的。连通强正则图是 共形刚性 的 (Steinerberger and Thomas 2024)。
完全图 对于所有
都是强正则的。平凡 单点图
的状态尚不清楚。关于
是否为强正则图的观点不一,尽管由于它没有明确定义的
参数,最好认为它不是强正则的 (A. E. Brouwer, 私人通信,2 月 6 日,2013 年)。
参数为 的非空非完全强正则图的 图的补图 是另一个强正则图,其参数为
。
许多强正则图在 Wolfram 语言 中实现为GraphData["StronglyRegular"].
节点数为 , 2, ... 的强正则图的数量分别为 1, 1, 2, 4, 3, 6, 2, 6, 5, ... (OEIS A076435),其中前几个如图所示。不是强正则的最小 正则图 是 环图
和 循环图
。
类似地,节点数为 , 2, ... 的连通强正则图的数量分别为 1, 0, 1, 2, 2, 3, 1, 3, 3, ... (OEIS A088741)。
Brouwer (2013) 推测,所有连通强正则图(其中假设 不是强正则的)都是 哈密顿图,除了 Petersen 图。
除了平凡 单点图 和 完全二分图
之外,恰好有七个已知的连通 无三角形 强正则图,如下表总结(Godsil 1995),其中六个如图所示。确定是否存在任何其他此类图仍然是一个未解决的问题。
| 图 | |
| 5 | 5-环图 |
| 10 | Petersen 图 |
| 16 | Clebsch 图 |
| 50 | Hoffman-Singleton 图 |
| 56 | Gewirtz 图 |
| 77 | M22 图 |
| 100 | Higman-Sims 图 |
下表给出了连通非完全强正则图的示例。
| 图 | |
| 方格图 | |
| 环图 | |
| 效用图 | |
| 八面体图 | |
| 完全二分图 | |
| 16-胞图 | |
| 广义四边形 GQ(2,1) | |
| 完全三分图 | |
| Petersen 图 | |
| 完全二分图 | |
| 5-三角形图 | |
| 5-鸡尾酒会图 | |
| (6,6)-完全二分图 | |
| (4,4,4)-完全三分图 | |
| (3,3,3,3)-完全 4-分图 | |
| 6-鸡尾酒会图 | |
| 13-Paley 图 | |
| 完全二分图 | |
| 7-鸡尾酒会图 | |
| 广义四边形 GQ(2,2) | |
| 6-三角形图 | |
| 完全三分图 | |
| 完全 5-分图 | |
| Clebsch 图 | |
| (4,4)-车图,Shrikhande 图 | |
| 完全二分图 | |
| (4,4)-车图的补图 | |
| 5-半立方体图 | |
| 完全 4-分图 | |
| 8-鸡尾酒会图 | |
| 17-Paley 图 | |
| 完全二分图 | |
| 完全三分图 | |
| 9-鸡尾酒会图 | |
| 完全二分图 | |
| 10-鸡尾酒会图 | |
| (7,2)-Kneser 图 | |
| 7-三角形图 | |
| 完全二分图 | |
| 11-鸡尾酒会图 | |
| 完全二分图 | |
| 12-鸡尾酒会图 | |
| (5,5)-车图 | |
| 25-Paley 图,25-Paulus 图 | |
| 26-Paulus 图 | |
| 完全二分图 | |
| 13-鸡尾酒会图 | |
| 广义四边形 GQ(2,4) | |
| Schläfli 图 | |
| 8-三角形图,Chang 图 | |
| 完全二分图 | |
| (8,2)-Kneser 图 | |
| 14-鸡尾酒会图 | |
| (29,14,6,7)-强正则图,29-Paley 图 | |
| 完全二分图 | |
| 15-鸡尾酒会图 | |
| 完全二分图 | |
| 16-鸡尾酒会图 | |
| 完全二分图 | |
| 17-鸡尾酒会图 | |
| (6,6)-车图 | |
| 9-三角形图 | |
| 完全二分图 | |
| (9,2)-Kneser 图 | |
| 18-鸡尾酒会图 | |
| 37-Paley 图 | |
| 完全二分图 | |
| 19-鸡尾酒会图 | |
| 完全二分图 | |
| 20-鸡尾酒会图 | |
| 41-Paley 图 | |
| 10-三角形图 | |
| (10,2)-Kneser 图 | |
| (7,7)-车图 | |
| 49-Paley 图 | |
| Hoffman-Singleton 图 | |
| Hoffman-Singleton 图 补图 | |
| 53-Paley 图 | |
| 11-三角形图 | |
| (11,2)-Kneser 图 | |
| Gewirtz 图 | |
| 61-Paley 图 | |
| (63,32,16,16)-强正则图 | |
| (8,8)-车图 | |
| 64-分圆图 | |
| 12-三角形图 | |
| (12,2)-Kneser 图 | |
| 73-Paley 图 | |
| M22 图 | |
| 13-三角形图 | |
| (13,2)-Kneser 图 | |
| (9,9)-车图 | |
| Brouwer-Haemers 图 | |
| 81-Paley 图 | |
| 89-Paley 图 | |
| 14-三角形图 | |
| (14,2)-Kneser 图 | |
| 97-Paley 图 | |
| (10,10)-车图 | |
| Higman-Sims 图 | |
| Hall-Janko 图 | |
| 101-Paley 图 | |
| 15-三角形图 | |
| (15,2)-Kneser 图 | |
| 109-Paley 图 | |
| 广义四边形 GQ(3,9) | |
| 113-Paley 图 | |
| 16-三角形图 | |
| (120,56,28,24)-强正则图 | |
| (120,63,30,36)-强正则图 | |
| 121-Paley 图 | |
| 125-Paley 图 | |
| 17-三角形图 | |
| 137-Paley 图 | |
| 149-Paley 图 | |
| 18-三角形图 | |
| 157-Paley 图 | |
| 局部 McLaughlin 图 | |
| 169-Paley 图 | |
| 19-三角形图 | |
| 20-三角形图 | |
| Berlekamp-van Lint-Seidel 图 | |
| Delsarte 图 | |
| (253,112,36,60)-强正则图 | |
| McLaughlin 图 | |
| Games 图 |
lambda=mu 的强正则图对应于对称平衡不完全区组设计 (West 2000, p. 465)。