设图 定义在顶点集
和 边集
上。则图
的构造序列(或 c-序列)是
上的线性顺序,其中每条边都出现在其两个端点之后。图
的构造数
定义为图
的不同构造序列的数量 (Kainen 2023)。
例如,对于路径图 ,其顶点集为 1, 2, 3,边集为 12, 23,共有 16 个可能的构造序列:(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),因此
。
下表总结了一些参数化图的构造数(参见 Kainen 2023),其中 是二项式系数,
是阶乘,
是双阶乘,
是伯努利数,而
是伽玛函数。Kainen等人 (2023) 提出了确定
的问题,并由 Tauraso (2024) 解决。