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 graph on an odd number of vertices such that degree of every vertex is the same odd number except for a single vertex whose degree is may be called a quasi-regular graph (Bozóki et al. 2020).
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.
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).