“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
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
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