Cooling Number

Given a finite, simple, undirected graph G, 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 G are cooled, and the cooling number CL(G) of G 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 P_4 (for which CL(P_4)=3) and the the complete bipartite graph K_(2,3) (for which CL(K_(2,3))=3).

By construction, the cooling number satisfies


where b(G) 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


and from below and above by


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

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

See also

Burning Number

Explore with Wolfram|Alpha


Bonato, A.; Marbach, T. G.; Milne, H.; and Mishura, T. "How to Cool a Graph." 7 Jan 2024.

Cite this as:

Weisstein, Eric W. "Cooling Number." From MathWorld--A Wolfram Web Resource.

Subject classifications