Regular Graph

A graph is said to be regular of degree if all local degrees are the same number . A 0-regular graph is an empty graph, a 1-regular graph consists of disconnected edges, and a two-regular graph consists of one or more (disconnected) cycles. The first interesting case is therefore 3-regular graphs, which are called cubic graphs (Harary 1994, pp. 14-15). Most commonly, "cubic graphs" is used to mean "connected cubic graphs." Note that -arc-transitive graphs are sometimes also called "-regular" (Harary 1994, p. 174).

A semirandom -regular graph can be generated using RegularGraph[k, n] in the Wolfram Language package Combinatorica` .

The following table lists the names of low-order -regular graphs.

	name for -regular graphs
3	cubic graph
4	quartic graph
5	quintic graph
6	sextic graph
7	septic graph
8	octic graph

Some regular graphs of degree higher than 5 are summarized in the following table.

	-regular graphs
6	Menger dual of the Gray configuration, halved Foster graph, Hoffman-Singleton Graph minus star, Kummer graph, Perkel graph, Reye graph, Shrikhande graph, 16-cell graph
7	doubly truncated Witt graph, bipartite double of the Hoffman-Singleton graph, Hoffman-Singleton graph, Klein graph
8	24-cell graph, line graph of the icosahedral graph
10	Conway-Smith graph, bipartite double of the Gewirtz graph, Gewirtz graph, Hall-Janko near octagon
12	line graph of the Hoffman-Singleton graph, Kronecker product of the icosahedral graph complement and the ones matrix , 600-cell graph
14	distance-2 graph of the Klein graph, graph
15	truncated Witt graph
16	bipartite double of the graph, graph, Schläfli graph
20	Brouwer-Haemers graph, Kronecker product of the Petersen line graph complement and the ones matrix
22	bipartite double of the Higman-Sims graph, Higman-Sims graph
27	Gosset graph
30	large Witt graph
36	Hall-Janko graph
42	Hoffman-Singleton graph complement
56	local McLaughlin graph
100	graph
112	McLaughlin graph
416	Suzuki graph

The numbers of nonisomorphic connected regular graphs of order , 2, ... are 1, 1, 1, 2, 2, 5, 4, 17, 22, 167, ... (OEIS A005177; Steinbach 1990).

For an -regular graph on nodes,

where is the edge count. Let be the number of connected -regular graphs with points. Then , , and when both and are odd. Zhang and Yang (1989) give for , and Meringer provides a similar tabulation including complete enumerations for low orders.

The following table gives the numbers of connected -regular graphs for small numbers of nodes (Meringer 1999, Meringer).

Sloane	A002851	A006820	A006821	A006822	A014377	A014378	A014381	A014382	A014384
class	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

Typically, only numbers of connected -regular graphs on vertices are published for as a result of the fact that all other numbers can be derived via simple combinatorics using the following facts:

1. Numbers of not-necessarily-connected -regular graphs on vertices can be obtained from numbers of connected -regular graphs on vertices.

2. Numbers of not-necessarily-connected -regular graphs on vertices equal the number of not-necessarily-connected -regular graphs on vertices (since building complementary graphs defines a bijection between the two sets).

3. For , there do not exist any disconnected -regular graphs on vertices.

The numbers of nonisomorphic not necessarily connected regular graphs with nodes, illustrated above, are 1, 2, 2, 4, 3, 8, 6, 22, 26, 176, ... (OEIS A005176; Steinbach 1990).

Wolfram Web Resources