一个 -正则 简单图 在 个节点上是强 -正则的,如果存在正整数 、 和 ,使得每个顶点有 个邻居(即,该图是一个 正则图),每对相邻顶点有 个共同邻居,并且每对不相邻顶点有 个共同邻居 (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)。