Cooling Number

Given a finite, simple, undirected graph , define cooling as a discrete-time process in which all nodes start off uncooled. At each subsequent step, one new uncooled node (called a source) is chosen to cool if such a node is available. If a node is cooled, then it remains in that state until the end of the process. Once a node is cooled, its uncooled neighbors become cooled in the next step. The process terminates when all nodes of are cooled, and the cooling number of is defined as the maximum number of steps for the cooling process to end (Bonato et al. 2024).

The cooling number of a graph measures the speed of a slow-moving contagion in a graph such that the lower the cooling number, the faster the contagion spreads (Bonato et al. 2024). Therefore, in contrast to the burning number of a graph--which gives the minimum number of rounds to burn all nodes--the cooling number gives the maximum number of rounds to cool all nodes.

The process is illustrated above for the path graph (for which ) and the the complete bipartite graph (for which ).

By construction, the cooling number satisfies

(1)

where is the burning number. This is because burning number corresponds to the first iteration in which a completely burnt graph first occurs, while the cooling number corresponds to the iteration in which no partially-uncooled graph remains.

The cooling number is bounded from above by

(2)

and from below and above by

(3)

where is the graph diameter (Bonato et al. 2024).

Values for some parametrized families of graphs are summarized below, where denotes the ceiling function.

family
complete graph
cycle graph
empty graph
path graph
star graph
wheel graph	2