冷卻數

給定一個有限、簡單、無向圖 ，定義冷卻為一個離散時間過程，其中所有節點最初都未冷卻。在隨後的每個步驟中，如果存在這樣的節點，則選擇一個新的未冷卻節點（稱為源）進行冷卻。如果一個節點被冷卻，那麼它將保持該狀態直到過程結束。一旦一個節點被冷卻，其未冷卻的鄰居將在下一步中被冷卻。當 的所有節點都被冷卻時，過程終止， 的冷卻數 定義為冷卻過程結束的最大步驟數 (Bonato et al. 2024)。

圖的冷卻數衡量圖中緩慢移動的傳染病的速度，冷卻數越低，傳染病傳播得越快 (Bonato et al. 2024)。因此，與圖的燃燒數（給出燃燒所有節點的最小輪數）相反，冷卻數給出冷卻所有節點的最大輪數。

上面的圖示說明了路徑圖 （其中 ）和完全二部圖 （其中 ）。

根據定義，冷卻數滿足

(1)

其中 是燃燒數。這是因為燃燒數對應於首次出現完全燃燒圖的第一次迭代，而冷卻數對應於沒有部分未冷卻圖剩餘的迭代。

冷卻數的上界為

(2)

下界和上界分別為

(3)

其中 是圖直徑 (Bonato et al. 2024)。

下表總結了一些引數化圖族的冷卻數值，其中 表示向上取整函式。

圖族
完全圖
圈圖
空圖
路徑圖
星圖
輪圖	2