Construction Number

Let a graph G=(V,E) be defined on vertex set V and edge set E. Then a construction sequence (or c-sequence) for G is a linear order on V union E in which each edge appears after both of its endpoints. The construction number c(G) of G is then defined as the number of distinct construction sequences for G (Kainen 2023).

For example, for the path graph P_3 with vertex set 1, 2, 3 and edge set 12, 23, there are 16 possible construction sequences (so c(P_3)=16), one of which is (1, 2, 3, 23, 13) (Kainen 2023).

The construction numbers for a number of parametrized graph are summarized in the table below (cf. Kainen 2023), where B_(2n) is a Bernoulli number.

See also

Assembly Number

Explore with Wolfram|Alpha


Kainen, P. C. "Construction Numbers: How to Build a Graph?" 25 Feb, 2023., N. J. A. Sequences A000142, A000182, A024255, A055546, A098694, and A210277 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Construction Number." From MathWorld--A Wolfram Web Resource.