TOPICS
Search

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).

PathGraphP3

For example, for the path graph P_3 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 c(P_3)=16.

The construction numbers for a number of parametrized graph are summarized in the table below (cf. Kainen 2023), where (n; k) is the binomial coefficient, n is a factorial, n!! is a double factorial, B_(2n) is a Bernoulli number, and Gamma(n) is the gamma function. The determination of c(K_n) was proposed by Kainen et al. (2023) and solved by Tauraso (2024).


See also

Assembly Number

Explore with Wolfram|Alpha

References

Kainen, P. C. "Construction Numbers: How to Build a Graph?" 25 Feb, 2023. https://arxiv.org/abs/2302.13186.Kainen, P. C.; Strong, R.; and Tilley, J. Problem 12401. Amer. Math. Monthly 130, 587, 2023.Sloane, N. J. A. Sequences A000142, A000182, A024255, A055546, A210277, and A374928 in "The On-Line Encyclopedia of Integer Sequences."Tauraso, R. Solution to Problem 12401. Amer. Math. Monthly. 2024. https://www.mat.uniroma2.it/~tauraso/AMM/AMM12401.pdf.

Cite this as:

Weisstein, Eric W. "Construction Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConstructionNumber.html