The construction number 
of a graph 
with vertex set 
and edge set 
is the number of distinct construction sequences for 
(Kainen 2023). For the graph 
, a construction sequence, or c-sequence, for 
is a linear order on 
in which each edge appears after both of its endpoints.
For example, for the path graph 
with vertex set 1, 2, 3 and
edge set 12, 23, there are a total of 16 possible construction
sequences: (1, 2, 3, 12, 23), (1, 2, 3, 23, 12), (1, 2, 12, 3, 23), (1, 3, 2, 12,
23), (1, 3, 2, 23, 12), (2, 1, 3, 12, 23), (2, 1, 3, 23, 12), (2, 1, 12, 3, 23),
(2, 3, 1, 12, 23), (2, 3, 1, 23, 12), (2, 3, 23, 1, 12), (3, 1, 2, 12, 23), (3, 1,
2, 23, 12), (3, 2, 1, 12, 23), (3, 2, 1, 23, 12), (3, 2, 23, 1, 12), giving 
.
The construction numbers for a number of parametrized graph are summarized in the table below (cf. Kainen 2023), where 
is the binomial coefficient,
is a factorial, 
is a double factorial,
is a Bernoulli number, and 
is the gamma function.
The determination of 
was proposed by Kainen et al. (2023) and solved
by Tauraso (2024).
| family | OEIS | construction number |
complete
graph  | A374928 |  |
cycle graph  | A024255 |  |
empty graph  | A000142 |  |
ladder rung graph  | A210277 |  |
path graph  | A000182 |  |
star graph  | A055546 |  |
