We have been taught since we were children not to disrupt the world around us. Keep quiet… Don’t make waves… Don’t start fires…

What would you do, however, if you were encouraged to set fires? That is, burn things down as quickly as possible. It may seem like an odd question, and such thoughts in real life might get you arrested. Luckily, as mathematicians, we can explore the darker side of our personality with pencil and paper.

To explain the relevance of this question, we just have to look to our everyday social networks.  Cutting edge social network research teaches us that emotions are indeed contagious, and can be communicated among our invisible web of social interactions. See the recent fascinating (albeit controversial in its methodology) paper on emotional contagion in Facebook published in the Proceedings of the National Academy of Sciences.  The paper formalizes our intuition about the spread of our thoughts and feelings to those we interact with. The familiar cliches of “misery loves company” or “smile and the world smiles with you” come to mind. It is interesting to note that the paper provides evidence that face-to-face contact is not necessary to spread emotional contagion.

Some of my recent research connects the ideas of spreading fires and the spread of emotional contagion. We attempted to quantify how quickly you can burn a given network, and developed a measure of how fast certain networks burn. In the process of graph burning, you start with a graph or network G, and assume at the start that every vertex is unburned. You then choose one vertex to burn. The fire propagates over time, so once a node is burned, then its neighbours are burned in the next step, then their neighbours in the following step, and so on. Once a vertex is burned, it stays in that state forever. In each step, you may choose a new unburned node to burn. The process continues until all nodes of G are burned.

For example, in a graph with all edges present, the fire simply burns the whole graph in one step. But for a path with n nodes, some calculating shows that the ceiling of n^(1/2)-many steps are needed to burn all nodes.

We define the burning number of a graph G to be the minimum number of steps needed to burn every node of G. One view is that the smaller the burning number, the easier it is to spread information/gossip/contagion in the graph. Burning is one way—really the first way we know of—to quantify how susceptible your network is to the spread of emotional contagion. This makes the topic of immediate interest to those working on the topic in complex networks, and also to the community of graph theorists working on dynamic graph problems such as Cops and Robbers.

Burning graphs is provably reducible to burning trees by considering the maximum burning number over spanning trees. We can compute the burning number exactly for some special graphs such as paths and cycles. There are bounds on the burning number in terms of the radius and diameter of a graph, and there are nice connections to certain domination parameters. From a computational perspective, we can prove that the burning number is NP-hard even for trees with maximum degree three. This means the burning number is quite tough to calculate for most graphs.

We conjecture that the burning number takes it maximum values for paths. We can prove something reasonably close; in particular, the burning number of G is bounded above by about 2n^(1/2).

Burning is a graph process that inspires many variations. For example, nodes could be burned only under certain conditions such as being adjacent to two or more burned vertices. This is reminiscent of graph bootstrap percolation which is a kind of deterministic cellular automata.

Burning is just the tip of the iceberg when studying dynamic graph processes. In my academic career, I have searched networks, cleaned them, burned them, and toppled them. There is no end mathematical research you can pursue with something so innocent looking as dots and lines. And the fact that graphs actually tie in with real-world networks is an added bonus.

Anthony Bonato