設圖 定義在頂點集
和 邊集
上。則圖
的構造序列(或 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) 解決。