一個 -正則 簡單圖
在
個節點上是強
-正則的,如果存在正整數
、
和
,使得每個頂點有
個鄰居(即,該圖是一個 正則圖),每對相鄰頂點有
個共同鄰居,並且每對不相鄰頂點有
個共同鄰居 (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)。