Let a graph 
be defined on vertex set 
and edge set 
. Then a construction sequence (or c-sequence) for 
is a linear order on 
in which each edge appears after both of its endpoints.
The construction number 
of 
is then defined as the number of distinct construction sequences
for 
(Kainen 2023).
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 |  |
