正則圖

如果一個 圖 的所有 區域性度數 都是相同的數字 ，則稱該圖為度為 的正則圖。0-正則圖是空圖，1-正則圖由不連通的邊組成，而2-正則圖由一個或多個（不連通的）環組成。因此，第一個有趣的例子是 3-正則圖，稱為立方圖 (Harary 1994, pp. 14-15)。最常見的是，“立方圖”用來表示“連通立方圖”。請注意，-弧傳遞圖 有時也稱為 “-正則圖” (Harary 1994, p. 174)。

在一個頂點數為奇數的圖中，如果除一個頂點的度數為 外，每個頂點的度數都是相同的奇數 ，則該圖可以稱為準正則圖 (Bozóki et al. 2020)。

可以使用以下方法生成半隨機 -正則圖：RegularGraph[k, n] 在 Wolfram 語言 包中Combinatorica` .

下表列出了低階 -正則圖的名稱。

	-正則圖的名稱
3	立方圖
4	四次圖
5	五次圖
6	六次圖
7	七次圖
8	八次圖

下表總結了一些度數大於 5 的正則圖。

	-正則圖
6	Gray 配置的門格爾對偶, 一半 Foster 圖, Hoffman-Singleton 圖 減星, Kummer 圖, Perkel 圖, Reye 圖, Shrikhande 圖, 16-胞圖
7	雙重截斷 Witt 圖, Hoffman-Singleton 圖 的二部雙圖, Hoffman-Singleton 圖, Klein 圖
8	24-胞圖, 正二十面體圖的線圖
10	Conway-Smith 圖, Gewirtz 圖 的二部雙圖, Gewirtz 圖, Hall-Janko 近似八邊形
12	Hoffman-Singleton 圖的線圖, 正二十面體圖補圖與全 1 矩陣 的克羅內克積, 600-胞圖
14	Klein 圖的距離-2 圖, 圖
15	截斷 Witt 圖
16	圖的二部雙圖, 圖, Schläfli 圖
20	Brouwer-Haemers 圖, Petersen 線圖補圖與全 1 矩陣 的克羅內克積
22	Higman-Sims 圖的二部雙圖, Higman-Sims 圖
27	Gosset 圖
30	大型 Witt 圖
36	Hall-Janko 圖
42	Hoffman-Singleton 圖補圖
56	區域性 McLaughlin 圖
100	圖
112	McLaughlin 圖
416	Suzuki 圖

階數為 , 2, ... 的非同構連通正則圖的數量為 1, 1, 1, 2, 2, 5, 4, 17, 22, 167, ... (OEIS A005177; Steinbach 1990)。

對於一個有 個節點的 -正則圖，

其中 是邊數。令 表示有 個頂點的連通 -正則圖的數量。那麼 , , 並且當 和 都是奇數時，。Zhang 和 Yang (1989) 給出了 ，其中 ，Meringer 提供了類似的表格，包括低階的完整列舉。

下表給出了節點數 較小時的連通 -正則圖的數量 (Meringer 1999, Meringer)。

Sloane	A002851	A006820	A006821	A006822	A014377	A014378	A014381	A014382	A014384
類別	cubic	quartic	quintic	sextic	septic	octic
4	1	0	0	0	0	0	0	0	0	0
5	0	1	0	0	0	0	0	0	0	0
6	2	1	1	0	0	0	0	0	0	0
7	0	2	0	1	0	0	0	0	0	0
8	5	6	3	1	1	0	0	0	0	0
9	0	16	0	4	0	1	0	0	0	0
10	19	59	60	21	5	1	1	0	0	0
11	0	265	0	266	0	6	0	1	0	0
12	85	1544	7848	7849	1547	94	9	1	1	0
13	0	10778	0	367860	0	10786	0	10	0	1
14	509	88168	3459383	21609300	21609301	3459386	88193	540	13	1
15	0	805491	0	1470293675	0	1470293676	0	805579	0	17
16	4060	8037418	2585136675					2585136741	8037796	4207
17	0	86221634	0		0		0		0	86223660
18	41301	985870522
19	0		0		0		0		0
20	510489
21	0		0		0		0		0
22	7319447
23	0		0		0		0		0
24	117940535
25	0		0		0		0		0
26	2094480864

13	0	0	0	0	0	0	0	0	0	0
14	1	0	0	0	0	0	0	0	0	0
15	0	1	0	0	0	0	0	0	0	0
16	21	1	1	0	0	0	0	0	0	0
17	0	25	0	1	0	0	0	0	0	0
18	985883873	42110	33	1	1	0	0	0	0	0
19	0		0	39	0	1	0	0	0	0
20				516344	49	1	1	0	0	0
21	0		0		0	60	0	1	0	0
22						7373924	73	1	1	0
23	0		0		0		0	88	0	1
24								118573592	110	1
25	0		0		0		0		0	130
26										2103205738

通常，只發布 時，在 個頂點上的連通 -正則圖的數量，這是因為所有其他數量都可以透過簡單的組合數學推匯出來，基於以下事實：

1. 在 個頂點上的非必要連通 -正則圖的數量可以從在 個頂點上的連通 -正則圖的數量中獲得。

2. 在 個頂點上的非必要連通 -正則圖的數量等於在 個頂點上的非必要連通 -正則圖的數量（因為構建互補圖定義了兩個集合之間的雙射）。

3. 對於 ，在 個頂點上不存在任何不連通的 -正則圖。

上面說明的，具有 個節點的非同構非必要連通正則圖的數量為 1, 2, 2, 4, 3, 8, 6, 22, 26, 176, ... (OEIS A005176; Steinbach 1990)。