On the Burning Number of the Generalized Heawood Graphs

Abstract

Graph burning is a discrete-time process that models the spread of contagion or information in a network. The burning number b(G) of a graph G is defined as the minimum number of discrete time steps required to ensure that all vertices are “burned”, assuming that in each step, a new vertex is ignited and the fire spreads to all adjacent vertices. Suppose n,k are two natural numbers where k ≥3 is odd and n≥k. The generalized Heawood graph, which is a cubic bipartite graph of girth 4 or 6, denoted as H(n,k) is the graph consisting of a 2n-cycle r₀r₁r₂...r_2n−1r₀ together with edges of the form r_2ir_2i+k,i = 0,1,2,...,n−1. Here the operations on the subscripts are reduced modulo 2n. In this paper, we propose ways to burn the generalized Heawood graphs and hence determine the burning number of all H(n,k) of girth 4 and that of H(2k,k) which is of girth 6.

Keywords: Burning number; generalized Heawood graphs.

2020 Mathematics Subject Classification. 68R10, 05C85, 91D30