• • • • • • • ## “School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16353
School of Mathematics
Title:   Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
Author(s):
 1 Mohammadreza Bidgoli 2 Behruz Tayfeh-Rezaie (Joint with A. Mohammadian)
Status:   Published
Journal: European J. Combin.
Vol.:  92
Year:  2021
Pages:   16pp
Supported by:  IPM
Abstract:
The r-neighbor bootstrap percolation on a graph is an activation process of the vertices. The process starts with some initially activated vertices and then, in each round, any inactive vertex with at least r active neighbors becomes activated. A set of initially activated vertices leading to the activation of all vertices is said to be a percolating set. Denote the minimum size of a percolating set in the r-neighbor bootstrap percolation process on a graph G by m(G, r). In this paper, we present upper and lower bounds on m(Knd, r), where Knd is the Cartesian product of d copies of the complete graph Kn which is referred as the Hamming graph. Among other results, when d goes to infinity, we show that m(Knd, r)=[(1+o(1))/((d+1)!)]rd if r >> d2 and n\geqslant r+1. Furthermore, we explicitly determine m(L(Kn), r), where L(Kn) is the line graph of Kn also known as triangular graph.

Download TeX format
back to top
scroll left or right