The construction number 
of a finite simple graph 
with vertex
set 
and edge set 
is the number of distinct construction sequences
for 
(Kainen 2025, p. 214). A construction sequence,
or c-sequence, for 
is a linear extension
of the partial order on 
generated by requiring each edge
to follow both of its endpoints. Each graph vertex
and edge is a distinct object in these orders.
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 several parametrized graphs are summarized in the table below (Kainen 2025, pp. 216-221). The cycle
graph formula applies for 
, and the other formulas apply for 
. Here, 
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). For the star graph 
on 
vertices, the cited OEIS A055546 gives the counts as absolute
values at index 
, rather than as its signed terms.
| family | OEIS | construction number |
complete
graph  | A374928 |  |
cycle graph  | A024255 |  |
empty graph  | A000142 |  |
ladder rung graph  | A210277 |  |
path graph  | A000182 |  |
star graph  | A055546 |  |
