Cooling Number

The cooling number of a finite, simple, undirected graph is the maximum number of steps needed to cool all its vertices in the following process. Initially, all vertices are uncooled. At each step, cooling first spreads from previously cooled vertices to their uncooled neighbors. One new uncooled graph vertex (called a source) is then chosen to cool if one is available. A cooled graph vertex remains cooled, and the process terminates when all vertices are cooled (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 vertices--the cooling number gives the maximum number of rounds to cool all vertices.

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

By construction, the cooling number satisfies

(1)

where is the burning number. The two quantities are the minimum and maximum, respectively, over choices of sources for the same process.

For a connected graph of graph order , the cooling number is bounded from above by

(2)

and from below and above by

(3)

where is the graph diameter and denotes the ceiling function (Bonato et al. 2024).

Values for some parametrized families of graphs are summarized below, where denotes the graph order.

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