Homology of graph burnings

DOI10.1016/J.TOPOL.2025.109486MaRDI QIDQ6934481zbMATH OpenFDO

Publication date 3 September 2025

Published in Topology and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TOPOL.2025.109486

burning homomorphism burning number category configuration space graph burning simplicial homology

Trees (05C05) Applications of graph theory (05C90) Graph complexes and graph homology (18G85) Simplicial sets, simplicial objects (18N50) Other homology theories in algebraic topology (55N35) Applications of graph theory to circuits and networks (94C15)

Review text

A burning process on a finite graph \(G\) is a discrete-time process for the choice of a free vertex \(v_t\) at each step \(t,t = 0, 1, \dots , T \), starting from an initial vertex \(v_0\), which becomes a burning vertex together with all its neighbors at the time \(t\). By a free vertex at each step \(i+1\) one means a vertex of \(G\) which was not burned during the burning process at steps \(0,1, \dots , i\). The burning process on \(G\) finishes when there are no free vertices of \(G\). The minimal burning process on \(G\) is a burning process with the minimal discrete time \(T_0\). The number \(T_0\) is called then the burning number of \(G\). Previously, burning of finite graphs was studied by several authors, see for example, [\textit{A. Bonato} et al., Internet Math. 12, No. 1--2, 85--100 (2016; Zbl 1461.05193)].\N\NIn the present paper, the authors study burning of graphs by using topological methods. Let \(P_T\) denote the path graph with length \(T\) where \(T\) corresponds to the end time of the burning process on \(G\). It turns out, every burning process on a graph \(G\) with the end time \(T\) induces a graph map of \(\lambda\colon G \to P_T\) on the vertices in a certain way. \(\lambda\) is called a burning homomorphism if it is a graph homomorphism. The conditions under which a graph does not admit a burning homomorphism are found (Theorem 3.10). The authors define also the category whose objects are graph burnings and morphisms are morphisms of graph burnings (Theorem 3.18 of the given paper) and study this category. In Section 4, the authors consider, for a given graph \(G\), the set \(\mathcal B(G)\) of all burnings of \(G\) and define the burning configuration space \(\Delta (G)\) of \(G\). \(\Delta (G)\) is actually a simplicial complex, a purely topological object, which allows the use of topological methods for its study. In Section 5, the authors study homology of burning configuration spaces and calculate homology groups for some special graphs. The burning numbers of path graphs are also evaluated.

Cites work

This page was built for publication: Homology of graph burnings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6934481)